Cho một số nguyên 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ó.

Input

Dòng 1: Một số nguyên N, số test đề bài (1<=N<=10^5)

Dòng 2: Gồm N số nguyên X (1<=X<=10^18)

Output

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

Ví dụ