Gọi ~f(N)~ là số cặp ~(a, b)~ sao cho ~a, b~ là ước nguyên dương của ~N~ và ~a \cdot b~ là một số chính phương. Cho ~T~ truy vấn, với mỗi truy vấn, cho hai số nguyên ~L, R~, hãy tính ~f(L) + f(L + 1) + \cdots + f(R)~ modulo ~10^9 + 7~ (~1 \leq T \leq 10^7~; ~1 \leq L \leq R \leq 10^7~).

Input

Dòng đầu tiên chứa số nguyên ~T~.

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ (~L \leq R~) thể hiện một truy vấn.

Output

In ra ~T~ dòng tương ứng đáp án của ~T~ truy vấn.

Scoring

• Subtask ~1~ (chiếm ~30\%~ số điểm): ~1 \leq T \leq 1000~, ~1 \leq L \leq R \leq 100~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq T \leq 10^5~, ~1 \leq L \leq R \leq 10^6~.

• Subtask ~3~ (chiếm ~30\%~ số điểm): ~1 \leq T \leq 10^5~, ~1 \leq L \leq R \leq 10^7~.

Sample Input 1

1
1 5

Sample Output 1

12