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.

Ràng buộc

● ~1 \le T \le 10^6~ ● ~2 \le X \le 10^6~

Ví dụ

Input

2
2
11

Output

500000
20779