Yêu cầu:

Cho X là một số nguyên tố, hãy xác định xem trong khoảng \([2,10^5]\) có bao nhiêu số nhận X là ước số nguyên tố nhỏ nhất của nó.

Dữ liệu vào Specification

• Dòng đầu tiên ghi một số nguyên N, số test đề bài \((1\le N\le10^5)\)
• N dòng tiếp theo, mỗi dòng ghi một số nguyên X \((1\le X\le 10^{18})\)

Dữ liệu ra Specification

• Gồm N số nguyên trên N dòng là kết quả ứng với N test.

Sample Input

    2
    2
    3

Sample Output

    50000
    16667