Số đẹp được định nghĩa như sau: Nếu X là một số chính phương, thì bình phương của X là một số đẹp.

Yêu cầu

Cho ~q~ truy vấn. Mỗi truy vấn là 2 số nguyên không âm ~l~ và ~r~, hãy tìm ra số lượng số đẹp trong khoảng từ ~l~ tới ~r~.

Input

• Dòng đầu tiên chứa số nguyên dương ~q~ ~(1≤q≤5*10^5)~.
• ~q~ dòng sau, mỗi dòng chứa 2 số nguyên không âm ~l~ và ~r~ ~(0≤l≤r≤10^{12})~, cách nhau một dấu cách.

Output

q dòng, mỗi dòng chứa kết quả truy vấn tươnng ứng.

Sample Input

3
1 10
2 100
3 1000

Sample Output

1
2
4

Subtask

• Có 25% số test ứng với 25% số điểm có ~q=1, 0≤l≤r≤10^6~;
• Có 25% số test ứng với 25% số điểm có ~q≤10^3, 0≤l≤r≤10^9~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.