Một số nguyên dương \(N\) là một số đặc biệt khi tổng các ước số của nó (trừ chính nó) lớn hơn \(M\) với \(M\) là một số nguyên dương được cho trước. Ví dụ với \(M = 5\) thì \(N = 6\) là số đặc biệt vì \(1 + 2 + 3 = 6 > 5\). Nhưng với \(M = 6\) hay \(M = 10\) thì \(N = 6\) không phải số đặc biệt.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có ba số nguyên dương lần lượt là \(L,R,X\). Bạn hãy đếm số đặc biệt có trong đoạn \([L;R]\) tính theo \(X\). Nói cách khác, bạn hãy đếm số thỏa mãn rằng tổng các ước số của nó (trừ chính nó) lớn hơn \(X\) có trong đoạn \([L;R]\).

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 \le Q \le 10^5)\).
• \(Q\) dòng tiếp theo mỗi dòng chứa ba số nguyên dương lần lượt là \(L,R,X\) \((1 \le L \le R \le 10^5, 1 \le X \le 10^5)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(Q,R \le 10^3\).

• Subtask \(2\) (\(20\%\) số điểm): Có \(R \le 10^4\) và \(X = 10\).

• Subtask \(3\) (\(30\%\) số điểm): Có \(X \le 10\).

• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
1 10 5
15 20 8

3
4