You are given an integer $N$. For each integer $i$ from 2 to $N$, assign a positive integer A[i] such that the following conditions hold:

• For any pair of integers $(i, j)$, if $i$ and $j$ are co-prime, then $A[i] != A[j]$.
• The maximum value among all $A[i]$ is the minimum possible.

Find the maximum value among all $A[i]$'s.

Note: A pair of integers $(i, j)$ is said to be co-prime when the greatest common divisor between them is 1.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line for each test case contains $N$ denoting an integer.

Output format

For each test case, print the maximum value among all $A[i]$'s in a new line.

Constraints

$1 \le T \le 10 \\ 2 \le N \le 10^5$