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