LCM

Time limit: 1.0s , Memory limit: 256M , Points: 0 (partial)

Cho hai số nguyên dương $L$ ~L~ và $R$ ~R~. Đếm số bộ ba số nguyên $(i,j,k)$ ~(i,j,k)~ thỏa mãn $L \le i < j < k \le R$ ~L \le i < j < k \le R~ và $\mathrm{LCM}(i,j,k) \ge i+j+k$ ~\mathrm{LCM}(i,j,k) \ge i+j+k~.

$\mathrm{LCM}(i,j,k)$ ~\mathrm{LCM}(i,j,k)~ được định nghĩa là bội chung nhỏ nhất của ba số nguyên $i,j$ ~i,j~ và $k$ ~k~.

Input

Dòng đầu tiên chứa số nguyên $T$ ~T~ $(1 \le T \le 10^4)$ ~(1 \le T \le 10^4)~ $-$ ~-~ số lượng test case.
Mỗi test case được mô tả trên một dòng chứa hai số nguyên $L$ ~L~ và $R$ ~R~ $(1 \le L \le R \le 10^5, \; L + 2 \le R)$ .

Output

Với mỗi test case, in ra trên một dòng là số lượng bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn.

Examples

Sample Input

2
3 6
14 16

Sample Output

3
1

Scoring

Subtask $1$ ~1~ với $20\%$ ~20\%~ số điểm: $T=1$ ~T=1~ và $|L-R| \le 200$ ~|L-R| \le 200~
Subtask $2$ ~2~ với $30\%$ ~30\%~ số điểm: $T=1$ ~T=1~
Subtask $3$ ~3~ với $20\%$ ~20\%~ số điểm: $L \le R \le 2000$ ~L \le R \le 2000~
Subtask $4$ ~4~ với $30\%$ ~30\%~ số điểm: Không có ràng buộc gì thêm

Notes

Ở test case đầu tiên, các bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn bao gồm:

$(3,4,5)$ ~(3,4,5)~
$(3,5,6)$ ~(3,5,6)~
$(4,5,6)$ ~(4,5,6)~

Comments

0

cocomelon_0202 commented on Feb. 18, 2025, 1:26 p.m.

lol

Link