Tricoin

 Tricoin

Problem Description

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:

1. He puts 1 coin in the 1st row.

2. then puts 2 coins in the 2nd row.

3. 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

Subtasks

Subtask 1 (48 points) : 1<=N<=105

Subtask 2 (52 points) : 1<=N<=109

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

Logic Test Case 1

Input (stdin)

3

3 5 7

Expected Output

2

2

3

Logic Test Case 2

Input (stdin)

7

7 5 4 3 8 9 5

Expected Output

3

2

2

2

3

3

2

code area

import java.util.Scanner;

class TestClass{

public static void main(String args[])

{

Scanner r=new Scanner(System.in);

int T=r.nextInt();

for(int t=0;t<T;t++)

{long sum=0,c=0;

int N=r.nextInt();

for(long i=1;i<=N;i++)

{

 sum=sum+i;

if(N==sum)

{

c=i;break;

}

else if((N<=sum)&&(N>sum-i))

{c=i-1;break;}

}

System.out.println(c);

}

}

}