Bedao Regular Contest 03 - PRIME

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.