Bedao Regular Contest 03 - PRIME

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hãy đếm số lượng số trong đoạn từ ~a~ đến ~b~ có ~k~ ước nguyên tố khác nhau. Cho ~Q~ truy vấn , mỗi truy vấn gồm ba số nguyên dương ~a, b, k~.

Input

  • Dòng đầu tiên chứa số nguyên dương ~Q~ là số lượng truy vấn. ~(1 \leq Q \leq 10^5)~

  • ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~a_i, b_i, k_i~ lần lượt mô tả các giá trị như trong yêu cầu bên trên. ~(1 \le a \le b \le 10^6, 1 \le k \le 7)~

Output

  • Ứng với truy vấn thứ ~i~, in ra một số nguyên duy nhất là số lượng số trong đoạn ~a_i~ đến ~b_i~ mà có ~k_i~ ước nguyên tố khác nhau. Mỗi truy vấn in ra trên một dòng.

Sample Input

2
3 6 2
7 10 1

Sample Output

1
3

Subtask

  • ~40\%~ số test có ~Q, a, b \le 10^3~
  • ~60\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.