Hôm nay bin9638 đang ôn thi 10.0 IELTS, đang ngồi học thì bỗng cậu thấy một gói thuốc trắng ở trên bàn nên tò mò nếm thử, không ngờ sau khi thử thì bin9638 lại thấy cơ thể nhẹ nhàng, lâng lâng và điều kì diệu là sau đó cậu có thể bay được.

Cậu ấy cứ bay lên cao, cao mãi, mãi khi tới những tầng mây thì cậu ấy gặp ông bụt ở đây. Ông bụt hứa sẽ tặng bin9638 một cuốn sách "Chinh phục 10 điểm ngữ văn" nếu cậu ấy trả lời được câu hỏi toán học của ông bụt.

Ông bụt định nghĩa một cặp số tình yêu là một cặp \(2\) số nguyên dương \(u,v\) ( \(u \le v\) ) thuộc đoạn \(l\) đến \(r\) sao cho ước chung lớn nhất của chúng không chia hết cho số nguyên dương \(n\).

Nhiệm vụ của bin9638 là đếm số lượng cặp số tình yêu với \(l\) và \(r\) cho trước. bin9638 rất muốn lấy được phần thưởng, hãy giúp cậu ấy nhé !

Input

• Dòng đầu tiên là số truy vấn \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng lần lượt là \(3\) số \(l,r,n\).

Output

• Gồm \(Q\) dòng với 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\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \le 10, n \le 1000, l \le r \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(Q \le 1000, n \le 10^3, l \le r \le 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): \(Q \le 10^5, n \le 10^{18}, l \le r \le 10^{18}\).

Example

1
3 5 2

5