Problem Description

There are $q$ queries. Each time, you are given a positive integer $n$. Ask how many positive integers $i$ with $i \le n$ satisfy that both $i$ and $n\bmod i$ are prime numbers.

Input Format

The first line contains one positive integer $q$.

The next $q$ lines each contain one positive integer $n$.

Output Format

Output $q$ lines. Each line answers one query.

5
5
55
555
5555
55555

1
3
22
93
447

Hint

This problem uses bundled tests.

Constraints:

• Subtask 1 (30 pts): $q = 1$.
• Subtask 2 (70 pts): no special constraints.

For all testdata, $1 \le n,q \le 2\times10^5$.

Luogu code length limit: 50 KB.

Translated by ChatGPT 5