Người ta định nghĩa, giá trị của hàm số ~f(k)~ là số lượng ước số dương của ~k~. Ví dụ ~k = 9~, ta có ~f(9) = 3~ (vì 9 có 3 ước số dương là 1, 3 và 9).

Một dãy ~A~ gồm ~n +1~ số nguyên dương ~a_0, a_1, a_2, \dots, a_n~ thỏa mãn:

• ~a_0 = 1~
• ~a_n = a_{n-1} + f(a_{n-1})~

Ta có 7 phần tử đầu tiên của dãy ~A~ là: ~a_0 = 1, a_1 = 2, a_2 = 4, a_3 = 7, a_4 = 9, a_5 = 12, a_6 = 18~. Trong đó, phần tử ~a_5~ được tính: ~a_5 = a_4 + f(a_4) = 9 + f(9) = 9 + 3 = 12~.

Yêu cầu:

Cho hai số nguyên dương ~p_i~ và ~q_i~. Với dãy ~A~ thỏa mãn các điều kiện trên, hãy đếm số phần tử trong dãy ~A~ có giá trị nằm trong đoạn ~[p_i; q_i]~.

Dữ liệu vào:

Cho trong file văn bản FCOUNT.INP, có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương ~t~ là số lượng đoạn ~p_i, q_i~ ~(1 \leq t \leq 10^5)~.
• Dòng thứ ~i~ trong ~t~ dòng tiếp theo: Mỗi dòng ghi hai số nguyên ~p_i, q_i~ ~(1 \leq i \leq t; 1 \leq p_i < q_i \leq 10^5)~, hai số được ghi cách nhau ít nhất một dấu cách.

Kết quả:

Ghi ra file văn bản FCOUNT.OUT, theo cấu trúc như sau:

• Dòng thứ ~i~ trong ~t~ dòng: Mỗi dòng ghi một số nguyên là số lượng phần tử tìm được trong dãy ~A~ tương ứng với đoạn ~[p_i; q_i]~ trong file dữ liệu vào.

Ví dụ:

Input: FCOUNT.INP

2
3 15
13 17

Output: FCOUNT.OUT

4
0