Description

Given $T$ queries, each contains a positive integer $n$. Find the all of the integer $m$ that satisfy the following conditions:

• $1 \le m \le n$
• $m$ is a perfect square number
• $m$ is a multiple of $3$

Find the quantity of $m$.

Input Format

Each test case contains multiple data sets. You will only receive the score for a test case if you pass all its data sets.

The first line contains an integer $T$.

The next $T$ lines each contains an integer $n$.

Output Format

$T$ lines, the quantity of $m$.

3
9
50
100

1
2
3

Hint

Example explanation

There are a total of three queries.

• For the first query, $m$ is $9$;

• For the second query, all $m$ are $9, 36$;

• For the third query, all $m$ are $9, 36, 81$.

Data Volume and Conventions

This problem is divided into subtasks. Your score in a subtask is the minimum score across all its test cases.

This problem uses subtask dependencies. You will not receive the score for a subtask unless you achieve full points on all its dependent subtasks.

For all of the cases, $1 \le T \le 3 \times 10^5,1 \le n \le 10^{18}$.