D. Doll Collector
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Everybody loves Pokémon dolls. They are the climax of every Pokémon game.

Ash started collecting some pokédolls and got addicted. Now he wants to spend all of his Pokédollars on new pokédolls to have the largest collection as possible.

Since Pokémon types grows very quickly, all Pokémon ID from $$$1$$$ to $$$10^{18}$$$ exists and the pokédoll of the Pokémon with ID $$$i$$$ costs $$$i$$$ Pokédollars.

You don't know exactly how many Pokédollars Ash has, so you will calculate the maximum number of distinct pokédolls he can buy for $$$n$$$ amounts of Pokédollars.

Input

The first line of input contains one integer, $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of queries.

The next $$$n$$$ lines contains, each, one integer, $$$s_i$$$ ($$$0 \le s_i \le 10^{18}$$$) — the amount of Pokédollars you estimate Ash has.

Output

For each query, print the maximum number of distinct pokédolls Ash could buy if he had the amount of Pokédollars of given query.

Examples
Input
3
2
3
9
Output
1
2
3
Input
2
52
60
Output
9
10