All Submissions


Problem Statement

Given two integers A and B, find the number of integers between A and B (inclusive) having even number of divisors.

Input

The first line contains T, the number of testcases.
Each testcase consists of two integers A and B.

Output

For each test case, print the answer in a new line.

Constraints

T <= 25000
1 <= A <= B <= 10^9

Sample Input


3
1 10
20 100
4 9


Sample Output


7
75
4


Problem Setter: Rohan Laishram

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0