Cho tập hợp ~S~ gồm các số nguyên dương đôi một khác nhau. Gọi ~f(S)~ là số cặp số nguyên dương ~(x, y)~ thỏa ~x \le y,\ \text{gcd}(x, y) = 1~ và ~\text{lcm}(x, y) \in S~.

Ví dụ: nếu ~S = \left \{ 1, 3 \right \}~ thì các cặp số thỏa mãn là ~(1, 1)~ và ~(1, 3)~, vì vậy ~f(S) = 2~.

Cho ~q~ truy vấn, mỗi truy vấn gồm ~3~ số ~(n, l, r)~, hãy đếm số tập hợp ~S~ khác nhau thỏa mãn:

• ~f(S) = n~

• Các phần tử thuộc tập hợp ~S~ nằm trong đoạn ~[l, r]~

• Số phần tử của tập hợp ~S~ là nhỏ nhất.

Hai tập hợp ~A~ và ~B~ được xem là khác nhau, nếu tồn tại một phần tử thuộc tập ~A~ mà không thuộc tập ~B~ và ngược lại.

Input

Dòng đầu tiên chứa số nguyên dương ~q~ (~1 \le q \le 10^6~) — số truy vấn của bài toán.

~q~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~n, l, r~ (~1 \le n \le 10^9~, ~1 \le l \le r \le 10^6~).

Output

In ra ~q~ dòng, dòng thứ ~i~ là đáp án của truy vấn tương ứng. Vì kết quả có thể rất lớn, hãy in phần dư khi lấy kết quả chia cho ~10^9 + 7~.

Sample Input 1

2
3 1 4
2 1 3

Sample Output 1

4
3

Notes

Ở truy vấn thứ nhất, các tập số thỏa mãn đề bài là ~\left \{ 1, 2, 3 \right \}~, ~\left \{ 1, 2, 4 \right \}~, ~\left \{ 1, 3, 4 \right \}~, ~\left \{ 2, 3, 4 \right \}~.

Ở truy vấn thứ nhất, các tập số thỏa mãn đề bài là ~\left \{ 1, 2 \right \}~, ~\left \{ 1, 3 \right \}~, ~\left \{ 2, 3 \right \}~.