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

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(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~ và ~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)~ thỏa mãn.

Examples

Sample Input

2
3 6
14 16

Sample Output

3
1

Scoring

• Subtask ~1~ với ~20\%~ số điểm: ~T=1~ và ~|L-R| \le 200~
• Subtask ~2~ với ~30\%~ số điểm: ~T=1~
• Subtask ~3~ với ~20\%~ số điểm: ~L \le R \le 2000~
• Subtask ~4~ với ~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)~ thỏa mãn bao gồm:

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