Chef has  $N$ doggo (dogs) , Lets number them $1$ to $N$.

Chef decided to build houses for each, but he soon realizes that keeping so many dogs at one place may be messy. So he decided to divide them into several groups called doggo communities. Let the total no. of groups be $K$ . In a community, paths between pairs of houses can be made so that doggo can play with each other. But there cannot be a path between two houses of different communities for sure. Chef wanted to make maximum no. of paths such that the total path is not greater then $K$.
Let’s visualize this problem in an engineer's way :)
The problem is to design a graph with max edge possible such that the total no. of edges should not be greater than the total no. of connected components.

-----INPUT FORMAT-----
- First line of each test case file contain $T$ , denoting total number of test cases.
- $ith$ test case contain only one line with a single integer $N$ , denoting the number of dogs(vertex)

-----OUTPUT FORMAT-----
- For each test case print a line with a integer , denoting the maximum possible path possible.

-----Constraints-----
- $1 \leq T \leq 10000$
- $1 \leq N \leq 10^9$ 

-----Sub-Tasks-----
- $20 Points$
- $1 \leq N \leq 10^6$ 

-----Sample Input-----
1

4

-----Sample Output-----
2

-----Explanation-----
4 houses can be made with  like this:

community #1  : [1 - 2  ]

community #2 :  [3 - 4 ]

or  [1 - 2 - 3]  , [ 4 ]

In both cases the maximum possible path is 2.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()
import math
from collections import defaultdict
from itertools import combinations_with_replacement,permutations
import bisect
import math as mt 
from functools import reduce
import time

def __starting_point():
    for _ in range(int(input())):
        n = int(input())
        a=1
        b=1
        c=(-2*n)
        dis = b * b - 4 * a * c  
        sqrt_val = math.sqrt(abs(dis))
        r1=(-b + sqrt_val)/(2 * a)
        # r2=(-b - sqrt_val)/(2 * a)

        # print(r1)
        r1 = math.floor(r1)+1
        print(n-r1+1)











__starting_point()

import random

def solve(n):
    b = 2*n + 3
    num = b - pow( b**2 - 4*n*(n+1), 0.5)
    ans = int(num // 2)
    return ans


for case in range(int(input())):
    n = int(input())
    print(solve(n))


# cook your dish here
import math
for _ in range(int(input())):
    n = int(input())
    x = (-1 + (8*n + 9)**0.5)*0.5
    ans = n - math.ceil(x) + 1
    print(ans)

# cook your dish here
import math
read = lambda : list(map(int,input().strip().split()))
rs = lambda :  int(input().strip())
t = rs()
ans = []
find_edges = lambda n,k : min(max_edges(n,k),k)
max_edges = lambda n,k : ((n-k+1) * (n-k)) >> 1
def find(n):
    # x = (n * (n+1));
    # other  = (2*n) + 3;
    l = (n >> 1) + (n%2); 
    r = n;
    while l + 1 < r:
        mid = l  + ((r-l) >> 1);
        if max_edges(n,mid) < mid:
            r = mid - 1;
        else:
            l = mid;
    if max_edges(n,r) >= r:
        return find_edges(n,r);
    else:
        return find_edges(n,l);
        

    
for _ in range(t):
    n = rs()
    ans.append(find(n))
print("\n".join([str(x) for x in ans]))

def fun(x):
    return (n*(n+1))-(((2*n)+1)*x)+(x**2)-(2*x)
from math import ceil
for _ in range(int(input())):


    n=int(input())

    l=0
    r=n+1

    while (l<=r):

        mid=(l+r)//2

        if fun(mid)>0:
            l=mid+1
            continue
        ans1=fun(mid)
        ans2=fun(mid-1)
        ##print(mid,ans1,ans2)
        if ans1<=0 and ans2>0:
            break

        if ans1<=0 and ans2<=0:
            r=mid-1

    mini=(n//2)+1
    maxi=mid-1

    ans1=((n-mid)*(n-mid+1))//2
    ans=max(maxi,ans1)
    ##print(mid,ans1)
    print(ans)




from collections import defaultdict
import sys
import math
import random
import bisect

sys.setrecursionlimit(10**6)
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


arr = [0]
for i in range(1,5*10**4):
    arr.append(arr[-1]+i)

for _ in range(int(input())):
    n = int(input())
    ind = bisect.bisect_left(arr,n)
    print(min(n-ind+1,ind*(ind-1)//2))

from collections import defaultdict
import sys
import math as mt
import random

sys.setrecursionlimit(10**6)
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()


ans = [0]*(10**6+1)
ans[2] = 1
ans[3] = 1
start = 3
for i in range(4,10**6+1):
    ans[i] = min((start*(start-1))//2,i-start+1)
    if ans[i]==ans[i-1]:
        start+=1

for _ in range(int(input())):
    n = int(input())
    print(ans[n])