Sherlock and Squares

Watson likes to challenge Sherlock's math ability. He will provide a starting and ending value describing a range of integers. Sherlock must determine the number of square integers within that range, inclusive of the endpoints.

Note: A square integer is an integer which is the square of an integer, e.g. .

Input Format

The first line contains , the number of test cases. 
Each of the next  lines contains two space-separated integers denoting  and , the starting and ending integers in the ranges.

Constraints

 

Output Format

For each test case, print the number of square integers in the range on a new line.

Sample Input

2
3  9
17  24

Sample Output

2
0

Explanation

Test Case #00: In range ,  and  are the two square integers. 
Test Case #01: In range , there are no square integers.

---

이 문제는 상당히 단순해 보이지만, 보이는 데로 코딩을 하면 테스트 케이스에서 시간 초과에 걸리게 된다. 처음에는 음? 왠 시간초과? 이 간단한 로직에서? 라고 생각을 하게 되는데, 핵심은 계산이 필요없는 숫자를 건너띄는 것이다. 즉, Square Number의 생성 규칙을 알고 있느냐 모르느냐이다.

1  -> 4  ->  9 ->  16 이런 식으로 번호가 증가되는데, 루프안에서 현재 탐지된 Square Number 다음의 숫자를 다음 Square Number 로 바로 건너뛰는 것이 핵심이다. 예를 들면 2 라는 값이 4, 3 이라는 값이 9, 4 라는 값이 16이 되는데, 4 다음에 9를 찾으면 되므로, 2 * 2 만큼을 건너뛰는 것이다. (4 + 2 * 2) 9 다음에 16을 찾으면 되므로, 3 * 2 만큼을 건너뛰게 된다. ( 9 + 3 * 2)