Nhiều truy vấn đếm số chính phương (Multiple Perfect-Square Count Queries)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $Q$ đoạn số nguyên. Truy vấn thứ $i$ được xác định bởi hai số nguyên dương $L_i$ và $R_i$ với $L_i \le R_i$.

Với mỗi truy vấn, hãy xác định số lượng số chính phương thuộc đoạn $[L_i,R_i]$. Các truy vấn độc lập với nhau và phải được trả lời theo đúng thứ tự xuất hiện trong dữ liệu vào.

Input

Dòng đầu chứa số nguyên dương $Q$ là số lượng truy vấn.

$Q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $L_i$ và $R_i$.

Output

In ra $Q$ dòng. Dòng thứ $i$ chứa số lượng số chính phương thuộc đoạn $[L_i,R_i]$.

Subtask

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

Ví dụ

Ví dụ 1

Input

4
1 10
15 35
36 36
37 63

Output

3
2
1
1

Giải thích

Bốn đoạn lần lượt chứa các số chính phương $\{1,4,9\}$, $\{16,25\}$, $\{36\}$ và $\{49\}$. Vì vậy bốn kết quả lần lượt là $3,2,1,1$.

Ví dụ 2

Input

4
1 1
2 3
99 100
100 121

Output

1
0
1
2

Giải thích

Đoạn $[1,1]$ chứa $1$; đoạn $[2,3]$ không chứa số chính phương; đoạn $[99,100]$ chỉ chứa $100$; đoạn $[100,121]$ chứa $100$ và $121$.

Ví dụ 3

Input

3
1000000000000000000 1000000000000000000
999999998000000001 1000000000000000000
999999998000000002 999999999999999999

Output

1
2
0

Giải thích

Hai số chính phương liên tiếp sát biên trên là $(10^9-1)^2=999999998000000001$ và $(10^9)^2=10^{18}$. Truy vấn thứ nhất chứa số thứ hai; truy vấn thứ hai chứa cả hai; truy vấn thứ ba nằm hoàn toàn giữa chúng nên không chứa số chính phương.