X and Y are having their main course meal over a candle light dinner at a posh restaurant. Instead of gazing into her eyes and enjoying the meal, X decides to play a game.

X gives two numbers A and B to Y and asks her to find the number of integers n that satisfy the following two conditions:

1. A <= n <= B
2. n is not divisible by any perfect square other than 1.

Your task is to help Y and find the answer for each of X's queries so that Y can enjoy her meal in peace.

Input

Input starts with an integer T (<= 100), denoting the number of test cases.

Each case is a line containing two integers A and B.

(1 <= A <= B <= 10^9)

Output

For each test case, print one number, which indicates the answer for the corresponding test case.

The answer for each test case must be in a new line.

Example

Input:
3
10 20
30 100
1000000 10000000

Output:
7
43
5471365

For example, the square-free numbers between 10 and 30 are 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30.