405252: GYM101858 D Doll Collector

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.

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.

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.

3
2
3
9

1
2
3

2
52
60

9
10