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\leq N\leq 10^5\))
• Dòng 2: Gồm \(n\) số nguyên \(x\) (\(1\leq X\leq 10^{18}\))

Output

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

Example

2
2
3

50000
16667