Multiple Perfect-Square Count Queries

Version: Phuoc Hung OJ Extended

Problem Statement

You are given $Q$ integer intervals. Query $i$ is described by two positive integers $L_i$ and $R_i$ with $L_i \le R_i$.

For each query, determine the number of perfect squares in $[L_i,R_i]$. The queries are independent and must be answered in their input order.

Input

The first line contains the positive integer $Q$, the number of queries.

The next $Q$ lines each contain two positive integers $L_i$ and $R_i$.

Output

Print $Q$ lines. Line $i$ contains the number of perfect squares in $[L_i,R_i]$.

Subtasks

• Subtask 1 (20%): $1 \le Q \le 100$ and $1 \le L_i \le R_i \le 10^6$.
• Subtask 2 (30%): $1 \le Q \le 2\cdot10^5$ and $1 \le L_i \le R_i \le 10^{12}$.
• Subtask 3 (50%): $1 \le Q \le 2\cdot10^5$ and $1 \le L_i \le R_i \le 10^{18}$.

Examples

Example 1

Input

4
1 10
15 35
36 36
37 63

Output

3
2
1
1

Explanation

The four intervals contain $\{1,4,9\}$, $\{16,25\}$, $\{36\}$, and $\{49\}$ respectively. Thus the answers are $3,2,1,1$.

Example 2

Input

4
1 1
2 3
99 100
100 121

Output

1
0
1
2

Explanation

$[1,1]$ contains $1$; $[2,3]$ contains no perfect square; $[99,100]$ contains only $100$; and $[100,121]$ contains both $100$ and $121$.

Example 3

Input

3
1000000000000000000 1000000000000000000
999999998000000001 1000000000000000000
999999998000000002 999999999999999999

Output

1
2
0

Explanation

The two consecutive perfect squares nearest the upper limit are $(10^9-1)^2=999999998000000001$ and $(10^9)^2=10^{18}$. The first query contains the latter; the second contains both; the third lies strictly between them and contains none.