Number

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

  Here are two numbers A and B (0 < A <= B). If B cannot be divisible by A, and A and B are not co-prime numbers, we define A as a special number of B.
  For each x, f(x) equals to the amount of x’s special numbers.
  For example, f(6)=1, because 6 only have one special number which is 4. And f(12)=3, its special numbers are 8,9,10.
  When f(x) is odd, we consider x as a real number.
  Now given 2 integers x and y, your job is to calculate how many real numbers are between them.

Input

  In the first line there is an integer T (T <= 2000), indicates the number of test cases. Then T line follows, each line contains two integers x and y (1 <= x <= y <= 2^63-1) separated by a single space.

Output

  Output the total number of real numbers.

Sample Input

2 1 1 1 10

Sample Output

0 4
Hint
For the second case, the real numbers are 6,8,9,10.

Hint

liuyiding

Source

2012 ACM/ICPC Asia Regional Tianjin Online

提交代码