# Triangle of Wealth

Medium
1
20.7% Acceptance

In a wealthy family known for their extensive gold mines, a member today brought N gold coins and aimed to construct a triangle with them. Quite the unique endeavor, isn't it?

The method to create this golden triangle is as follows:

• Place 1 coin in the 1st row.
• Follow with 2 coins in the 2nd row.
• Next, 3 coins in the 3rd row.
• Continue in this manner as depicted in the image below.

The goal is to form a triangle with the maximum possible height using no more than N coins. Can you determine the tallest triangle that can be built?

### Input

The input begins with a single integer T, indicating the number of test cases.

Each test case is described in one line, containing an integer N — the number of gold coins available.

### Output

For each test case, output a single line with one integer: the maximum height of the triangle that can be created.

### Constraints

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

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

## Sample Test Cases (and explanation)

### Case #1:

Input:

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

Output:

``````2
2
3``````

#### Explanation

Test 1: It's not possible to form a triangle taller than 2 levels with only 3 gold coins.

Test 2: Similarly, 5 gold coins are insufficient for a triangle taller than 2 levels.

Test 3: With 7 gold coins, a triangle of height 3 levels can be formed, requiring at least 10 gold coins for a taller structure.