Sad powers

You're given Q queries of the form (L, R).

For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = ap.

Input

The first line contains the number of queries Q (1 ≤ Q ≤ 105).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).

Output

Output Q lines — the answers to the queries.

Example

Input

6 1 4 9 9 5 7 12 29 137 591 1 1000000

Output

2 1 0 3 17 1111

Note

In query one the suitable numbers are 1 and 4.

inputFormat

Input

The first line contains the number of queries Q (1 ≤ Q ≤ 105).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).

outputFormat

Output

Output Q lines — the answers to the queries.

Example

Input

6 1 4 9 9 5 7 12 29 137 591 1 1000000

Output

2 1 0 3 17 1111

Note

In query one the suitable numbers are 1 and 4.

样例

6
1 4
9 9
5 7
12 29
137 591
1 1000000

2
1
0
3
17
1111

</p>