D. You Have Been Grid Squared
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A grid of size $$$n \times n$$$ is constructed in the following way:

The first row of the grid consists of the numbers $$$1, 2, 3, \dots, n$$$ (in that order).

Then, each other cell in the grid will be filled with the square of the number in the cell above it.

Given an integer $$$n$$$, count the number of distinct integers in an $$$n \times n$$$ grid.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) – the number of rows and columns in the grid.

Output

For each testcase, output a single integer — the number of distinct integers in the grid.

Example
Input
2
2
3
Output
3
7
Note

The grid in the first testcase:

12
14

The grid in the second testcase:

123
149
11681