Znajdź ilość naturalnych rozwiązań (x≥1, y≥1) nierówności x²+y²<n, gdzie (0<n<2 147 483 647).

Przykładowo, dla n=10 istnieje 4 rozwiązania: (1,1), (1,2), (2,1), (2,2).

Input

W pierwszej linijce wejścia podana jest ilość testów K. W kolejnych K linijkach podane są wartości liczby n.

Output

Na wyjściu trzeba dla każdej wartości n wyświetlić w oddzielnej linijce ilość naturalnych rozwiązań nierówności.

Example

Input:
2
10
11

Output:
4
6