Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

C. Sad powers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.