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

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\)