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