Trong ngày lễ tình yêu, ông Bụt mang tới cho các cặp đôi một số nguyên dương ~n~. Được biết một cặp số tình yêu là một cặp gồm 2 số nguyên dương ~(u, v)~ (với ~u \le v~) sao cho ~\gcd(u, v)~ không chia hết cho ~n~.

Để giành được tình cảm của crush, các bạn cần đếm xem có bao nhiêu cặp số tình yêu mà giá trị ~u, v~ nằm trong đoạn ~[l, r]~. Nói cách khác, bài toán yêu cầu đếm số cặp ~(u, v)~ thỏa mãn ~l \le u \le v \le r~ và ~\gcd(u, v)~ không chia hết cho ~n~.

Được biết bạn là thần đồng tin học, ông Bụt mang tới ~Q~ bộ câu hỏi như thế và thách thức bạn.

Input:

Nhập từ tệp LOVE.INP:

• Dòng đầu tiên chứa một số nguyên ~Q~ — số truy vấn (~1 \le Q \le 10^5~).
• Mỗi truy vấn gồm ba số nguyên dương ~l, r, n~ (~1 \le l \le r \le 10^{18}~, ~1 \le n \le 10^{18}~).

Output:

Xuất ra tệp LOVE.OUT:

• Gồm ~Q~ dòng, mỗi dòng là kết quả của truy vấn tương ứng khi chia lấy dư cho ~10^9 + 7~.

Subtasks

Sample Input

1
3 5 2

Sample Output

5

Giải thích

Các cặp số ~(u,v)~ với ~3 \le u \le v \le 5~ là: ~(3,3), (3,4), (3,5), (4,4), (4,5), (5,5)~.

• ~\gcd(3,3) = 3~ không chia hết cho ~2~.
• ~\gcd(3,4) = 1~ không chia hết cho ~2~.
• ~\gcd(3,5) = 1~ không chia hết cho ~2~.
• ~\gcd(4,4) = 4~ chia hết cho ~2~. (Loại)
• ~\gcd(4,5) = 1~ không chia hết cho ~2~.
• ~\gcd(5,5) = 5~ không chia hết cho ~2~.

Các cặp số thoả mãn là: ~(3,3), (3,4), (3,5), (4,5), (5,5)~. Có tổng cộng 5 cặp.