Số tự nhiên \(m\) được gọi là ước nguyên tố của số nguyên dương \(n\) nếu \(n\) chia hết cho \(m\) và \(m\) là số nguyên tố.

Ví dụ: Số \(12\) có \(2\) ước nguyên tố là \(2\) và \(3\); số \(30\) có \(3\) ước nguyên tố là \(2\), \(3\) và \(5\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên \(a, b, k\). Với mỗi truy vấn, hãy xác định số lượng các số nguyên \(x\) thỏa mãn: \(a \le x \le b\) và có số lượng ước nguyên tố không nhỏ hơn \(k\).

Input

• Dữ liệu vào có cấu trúc:
  • Dòng thứ nhất chứa số nguyên dương \(Q\) là số lượng truy vấn \((1 \le Q \le 10^5)\).
  • \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a, b, k\) \((1 \le a \le b \le 10^6;\ 0 \le k \le 7)\).

Output

• Ghi ra \(Q\) dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

Example

1
25 30 2

3

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài thỏa mãn: \(Q = 1;\ 1 \le a \le b \le 10^3\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(Q = 1;\ 10^3 < a \le b \le 10^6\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.