## CUTCAKE - Eat all the brownies !

no tags

BrownieDude was given the job of cutting cake at a party for serving the guests. But BrownieDude is both lazy and hungry, so he wants to cut the cake into maximum number of pieces with minimum number of cuts and go off to eating brownies.

The host of the party says that BrownieDude can cut the cake into unequal pieces but cannot cut in more than one plane.(Only vertical cuts are allowed.) Given the number of guests, find the number of cuts sufficient to generate the cake pieces.

### Input

First line contains 't', the number of test cases. 't' lines follow. (1 <= t <= 1000)

Each line denotes the number of guests. (1 <= n <= 10^11)

### Output

One number denoting the number of cuts.

Note: It is guaranteed that an integer solution will always exist.

Example Input:

```2
1
2```

Example Output:

```0
1```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````def f(N):
return (N * N + N + 2) >> 1
T = int(input())
for i in range(T):
N = int(input())
low, high, mid, best = 0, N, 0, N
while low <= high:
mid = (low + high + 1) >> 1
if f(mid) >= N:
best = mid
high = mid - 1
else:
low = mid + 1
print(best)``````
Copy The Code &

Input

cmd
2
1
2

Output

cmd
0
1

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<stdio.h>
int main()
{
long long t,n,ps,cut;
scanf("%lld",&t);
while(t--)
{
ps=1;
cut=0;
scanf("%lld",&n);
while(ps<n)
{
cut++;
ps+=cut;
}
printf("%lld\n",cut);
}
return 0;
}``````
Copy The Code &

Input

cmd
2
1
2

Output

cmd
0
1