G. Tuesday Night Fever (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. In this version, $$$n \le 10^{12}$$$.

Armando is a very special being. Not only because he shines a little brighter on Tuesday nights, but because he has two incredible powers... which, unfortunately, only work on Tuesday nights.

His powers are the following:

  1. He can find a party with exactly the number of people he wants.
  2. Every time he enters a party, all the people present start greeting each other, one by one. Each greeting consists of both people solemnly saying: — maestro.

Armando, being very, very special (and a bit obsessive), wants to hear the word maestro exactly $$$n$$$ times during one Tuesday night.

But there is a serious problem. When Wednesday arrives, his powers disappear completely. So Armando needs to get exactly $$$n$$$ maestros attending the smallest possible number of parties.

Armando can attend several parties during the night, and at each one he can choose how many people there will be. The total number of maestros he hears is the sum of the maestros generated at all the parties he attends.

Your task is to help Armando. Given a number $$$n$$$, determine the minimum number of parties he needs to attend to hear exactly $$$n$$$ maestros.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$), the number of test cases.

Each of the next $$$t$$$ lines contains an integer $$$n$$$ ($$$1 \le n \le 10^{12}$$$), the exact number of maestros Armando wants to hear.

Output

For each test case, print a single integer: the minimum number of parties needed to get exactly $$$n$$$ maestros.

Example
Input
5
1
2
3
42
10
Output
1
2
1
2
1
Note

For $$$n = 10$$$, Armando can attend a single party with $$$5$$$ people:

  • Armando — maestro — Chamir
  • Armando — maestro — Geordie Maddie
  • Armando — maestro — Mishi
  • Armando — maestro — Oliver
  • Chamir — maestro — Geordie Maddie
  • Chamir — maestro — Mishi
  • Chamir — maestro — Oliver
  • Geordie Maddie — maestro — Mishi
  • Geordie Maddie — maestro — Oliver
  • Mishi — maestro — Oliver