Description

There are Infinite People Standing in a row, indexed from 1.A person having index 'i' has strength of (i*i).You have Strength 'P'. You need to tell what is the maximum number of People You can Kill With your Strength P.You can only Kill a person with strength 'X' if P >= 'X' and after killing him, Your Strength decreases by 'X'

Input

First line contains an integer 'T' - the number of testcases,Each of the next 'T' lines contains an integer 'P'- Your Power.Constraints:1<=T<=100001<=P<=1000000000000000

Output

For each testcase Output The maximum Number of People You can kill.

Sample Input 1

1
14

Sample Output 1

3

Solution

# 实际上是问小于p的累加乘方的序号
if __name__ == '__main__':
    T = int(input())
    while T:
        T -= 1
        p = int(input())
        i = 1
        while p >= i**2:
            p -= i**2
            i += 1
        print(i)