Jerry

题号：NC222897
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Although Jerry is a mouse, he likes perfect square numbers. If a number can be expressed as the square of an integer, it is called perfect square numbers. Jerry can use magic to move forward or backward a distance of any perfect square numbers, which costs a grain of rice each time. And the position after each use of magic can not be behind the initial position or more than $10^5$ distance in front of the initial position. Next, there are $q$ questions, each time asking how much rice at least it takes for Jerry to move forward $d_i$ .Note that each question is an independent one.

输入描述:

The first line contains an integer $q(1 \leq q \leq 100000)$ ,which represents the number of questions you need to solve.

Each of the next $q$ lines contains an integer $d_i(1 \leq d_i \leq 100000)$ ,which represents the distance Jerry want to move forward.

输出描述:

For each query, print an integer to represent the minimum cost of rice.

示例1

输入

复制

2
8 
7

输出

复制

2
2

说明

In the first query: 0 -> 4 -> 8.
In the second query: 0 -> 16 -> 7.