Cho một mảng A chứa các số nguyên với các ràng buộc sau:

• Mảng A chứa các phần tử theo thứ tự tăng dần, giá trị đầu tiên trong mảng \(A\) là \(1\).

• Giá trị \(i\) xuất hiện \(i×floor(sqrt(i))+ceil(i/2)\) lần trong mảng \(A, i = 1, 2\), ....

• Tất cả các phần tử đều lớn hơn hoặc bằng 1.

Một số phần tử đầu tiên dãy \(A = [1,1,2,2,2,3,3,3,3,3,….]\)

Yêu cầu: : Cho \(Q\) truy vấn có dạng :

~L, R~∶ Tìm số lượng giá trị khác nhau có mặt trong dãy con~ A[L..R]~.

Input

• Dòng 1 chứa số nguyên \(Q (1≤ Q ≤ 100000)\);

• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L,R (1≤ L ≤ R ≤ 10^{13} )\);

Output

• Ghi \(Q\) dòng, mỗi dòng ghi kết quả của truy vấn tương ứng.

Sample Input

2
1 3
1 6

Sample Output

2
3