B. Jumps

B. Jumps

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are standing on the OXOX-axis at point 00 and you want to move to an integer point x>0x>0.

You can make several jumps. Suppose you're currently at point yy (yy may be negative) and jump for the kk-th time. You can:

• either jump to the point y+ky+k
• or jump to the point y−1y−1.

What is the minimum number of jumps you need to reach the point xx?

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first and only line of each test case contains the single integer xx (1≤x≤1061≤x≤106) — the destination point.

Output

For each test case, print the single integer — the minimum number of jumps to reach xx. It can be proved that we can reach any integer point xx.

Example

input

Copy

5
1
2
3
4
5

output

Copy

1
3
2
3
4

Note

In the first test case x=1x=1, so you need only one jump: the 11-st jump from 00 to 0+1=10+1=1.

In the second test case x=2x=2. You need at least three jumps:

• the 11-st jump from 00 to 0+1=10+1=1;
• the 22-nd jump from 11 to 1+2=31+2=3;
• the 33-rd jump from 33 to 3−1=23−1=2;

Two jumps are not enough because these are the only possible variants:

• the 11-st jump as −1−1 and the 22-nd one as −1−1 — you'll reach 0−1−1=−20−1−1=−2;
• the 11-st jump as −1−1 and the 22-nd one as +2+2 — you'll reach 0−1+2=10−1+2=1;
• the 11-st jump as +1+1 and the 22-nd one as −1−1 — you'll reach 0+1−1=00+1−1=0;
• the 11-st jump as +1+1 and the 22-nd one as +2+2 — you'll reach 0+1+2=30+1+2=3;

In the third test case, you need two jumps: the 11-st one as +1+1 and the 22-nd one as +2+2, so 0+1+2=30+1+2=3.

In the fourth test case, you need three jumps: the 11-st one as −1−1, the 22-nd one as +2+2 and the 33-rd one as +3+3, so 0−1+2+3=40−1+2+3=4.

=========================================================================

首先对于能够用 1+2+...n表示的，那么肯定首选n种

1+2+3+............+n  =  y

y ->n

y-1  y的基础之上减1

y-2 第一步变成-1

y-3 第二部变成-1

。。

y-n+1 第n-1部分变成-1

y-n   也就是1+2+3....+n-1 会被上一次循环拦截掉

#include 
using namespace std;
typedef long long int ll;
 
int main()
{
 
 
  int t;
 
  cin>>t;
 
  while(t--)
  {
      int n;
 
      cin>>n;
 
      for(ll i=1;;i++)
      {
          ll now=(i)*(i+1)/2;
 
          if(now==n)
          {
              cout<
              break;
          }
          else if(now==n+1)
          {
              cout<1<
              break;
          }
          else if(now>n)
          {
              cout<
              break;
 
          }
      }
  }
    return 0;
}