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ò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

Gồm ~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.

Scoring

Sample Input 1

1
25 30 2

Sample Output 1

3

Notes

Từ ~25~ đến ~30~ có ~3~ số có từ ~2~ ước nguyên tố trở lên đó là ~26, 28~ và ~30~.

Cụ thể:

• ~26~ có ~2~ ước nguyên tố là ~2~ và ~13~

• ~28~ có ~2~ ước nguyên tố là ~2~ và ~7~

• ~30~ có ~3~ ước nguyên tố là ~2, 3~ và ~5~