For a given positive integer y (y > 1), if we can find a largest integer k and a smallest positive integer x, such that x^k=y, then the power of y is regarded as k.

Calculate the sum of the power of the integers from a to b. (2<= a <= b <=10¹⁸)

Input

The input consists of multiple test cases.

For each test case, there is one line containing two integers a and b.

End of input is indicated by a line containing two zeros.

Output

For each test case, output the sum of the power of the integers from a to b.

Example

Input:
2 10
248832 248832
0 0

Output:
13
5