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);

}

}

}

Post a comment

0 Comments