Cho số nguyên tố X, nhiệm vụ của bạn là đếm xem trong đoạn từ 1 đến ~10^6~, có bao nhiêu số mà khi phân tích số đó ra thừa số nguyên tố thì thừa số nguyên tố nhỏ nhất là X.

INPUT

• Dòng đầu tiên chứa số nguyên T, số lượng bộ test
• T dòng tiếp theo, mỗi dòng chứa một số nguyên tố X

OUTPUT

Với mỗi số nguyên tố X, ghi ra một số nguyên duy nhất là số lượng số khi phân tích ra thừa số nguyên tố thì giá trị nguyên tố nhỏ nhất là X, kết quả ghi ra trên mỗi dòng.

vÍ DỤ:

INPUT

2 
2
11

OUTPUT

500000
20779

RÀNG BUỘC

• ~1<=T<=10^6~
• ~2<=X<=10^6~