## Problem

### Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn't it strange?

Chef has a unusual way of forming a triangle using gold coins, which is described as follows:

• He puts 1 coin in the 1st row.
• then puts 2 coins in the 2nd row.
• then puts 3 coins in the 3rd row.
• and so on as shown in the given figure.

Chef is interested in forming a triangle with maximum possible height using at most N coins. Can you tell him the maximum possible height of the triangle?

### Input

The first line of input contains a single integer T denoting the number of test cases.

The first and the only line of each test case contains an integer N denoting the number of gold coins Chef has.

### Output

For each test case, output a single line containing an integer corresponding to the maximum possible height of the triangle that Chef can get.

### Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 109

• Subtask 1 (48 points) : 1 ≤ N ≤ 105
• Subtask 2 (52 points) : 1 ≤ N ≤ 109

Input

Output

```3
3
5
7```
```2
2
3```

### Explanation:

Test 1: Chef can't form a triangle with height > 2 as it requires atleast 6 gold coins. Test 2: Chef can't form a triangle with height > 2 as it requires atleast 6 gold coins. Test 3: Chef can't form a triangle with height > 3 as it requires atleast 10 gold coins.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````  #include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned long long
#define pb push_back
#define ss second
#define ff first
#define fr(m) for (int i = 0; i  <  m; i++)
#define fro(m) for (int i = 1; i  <  m; i++)
#define frj(m) for (int j = 0; j  <  m; j++)
#define frr(n) for (int i = n; i >= 0; i--)
#define nl '\n'
#define yes cout << "YES" << nl
#define no cout << "NO" << nl
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " " << x << endl;
#define fast_io (ios_base::sync_with_stdio(false), cin.tie(NULL));

ll fact(ll n)
{
if (n == 0)
return 1;
ll res = 1;
for (ll i = 2; i  < = n; i++)
res = res * i;
return res;
}
ll nPr(ll n, ll r) { return fact(n) / fact(n - r); }
ll nCr(ll n, ll r) { return fact(n) / (fact(r) * fact(n - r)); }
ll gcd(ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll mypow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = (ans * a);
b /= 2;
a = (a * a);
}
return ans;
}
bool isPrime(ll n)
{
if (n  < = 1)
return false;
for (ll i = 2; i  < = sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}

#define PI 3.141592653589793238;
#define INF LONG_LONG_MAX;
#define MOD 1e9 + 7;

//////////////////////////////////Code Start/////////////////////////////////////

void solve()
{
int n, i, m;
cin >> n;
if (n == 1)
{
cout << 1 << endl;
return;
}
for (i = 1; i  <  n; i++)
{
m = (i * i + i) / 2;
if (m > n)
break;
}
cout << i - 1 << endl;
}

int main()
{
fast_io;
int TC = 1;
cin >> TC;
while (TC--)
solve();
}``````
Copy The Code &

Input

cmd
3 3 5 7

Output

cmd
2 2 3

## Demonstration

CodeChef solution TRICOIN  - Coins and Triangle  Codechef solution in C,C++