Cho \(Q\) truy vấn \(l\) \(r\) \(x\). Với mỗi truy vấn, hãy đếm số lượng số có tổng các ước thực sự(không kể chính nó) lớn hơn \(x\) nằm trong đoạn \([L..R]\).

Input

Dữ liệu nhập từ tệp QUERY.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương \(Q(1 \leq Q \leq 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa mỗi truy vấn \(l\) \(r\) \(x\). \((1 \leq l \leq r \leq 10^5, 1 \leq x \leq 10^5)\)

Output

Dữ liệu in ra tệp QUERY.OUT theo cấu trúc như sau:
- Gồm \(Q\) dòng, mỗi dòng là kết quả của mỗi truy vấn tương ứng.

Subtask

• Subtask \(1(30\%)\): \(Q,R \leq 10^3\).
• Subtask \(2(20\%)\): \(x \leq 10\)
• Subtask \(3(50\%)\): Ràng buộc gốc.

2
1 10 5
15 20 8

3
4