Migrated from Lutece 2667 Violet mag Veilchen

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。

——《Sincerely (off vocal)》

Violet 最喜欢的花是紫罗兰（一说东北堇菜）。在 C·H 邮政公司不远有一个中心公园，公园中有一个巨大的圆形花坛，种植花朵的区域半径为 $n$。也就是说这个花坛能种花的区域可以用二维平面上的一个圆形区域 $x^2+y^2\le n^2$ 描述。花坛内种了很多花，其中所有整数点都种了一株紫罗兰。整数点指的是对于坐标为 $(x,y)$ 的点，$x$ 和 $y$ 均为整数的点。

Violet 想知道这个花坛中到底种了多少紫罗兰，但是这个花坛太大，Violet 数不过来，请帮帮她。作为回报，她可以帮你写一封信。

Input

本题有多组数据，第一行输入一个整数 $T\ (1\le T\le 50)$，表示数据组数。

接下来 $T$ 行，每行一个整数 $n\ (1\le n\le 10^9)$，表示这个花坛的半径。

Output

输出 $T$ 行，每行一个整数，表示花坛中紫罗兰的数量。

Samples

3
1
114514
1919810

5
41197137077
11578875162305

Resources

2021 UESTC ICPC Training for Math and Geometry