You are given an undirected simple graph $G$ containing exactly $n$ distinct nodes.

The nodes are numbered from $1$ to $n$.

Suppose that $(u,v)$ is an edge of $G$ if and only if $u \cdot v$ is a perfect square.

Please compute the number of the connected components of $G$.

Input Format

• The first line contains a single integer $T$ — the number of test cases.
• Each test case consists one positive integer $n$ — the number of distinct nodes.

Output Format

• For each testcase, output the number of the connected components of $G$.

 Constraints

• $1 \leq T \leq 10^4$
• $1 \leq n \leq 2 \cdot 10^5$
• The sum of $n$ over all test cases does not exceed $10^7$.