Question

Nishant does pretty weird stuff. Today, he wants to create a weird sequence.

According to Nishant, a sequence A of length N is called weird if:

N≥3

2⋅Ai>Ai−1+Ai+1 ∀i∈{2,3,4....,N−1}

Nishant wants to construct a long weird sequence to impress his weird friends, but there's a problem: he only knows how to count up to K, so the sequence can only contain integers in the range [1,K].

Help Nishant determine the length of the longest weird sequence he can construct using only integers from 1 to K.

Input Format

The first line contains a single integer T denoting the number of testcases. The description of T testcases follows.

The first and only line of each testcase contains a single integer K.

Output Format

For each testcase, print one line containing a single integer - the maximum length of a weird sequence which can be obtained using only integers in [1,K].

Constraints

1≤T≤105

2≤K≤109

Sample Input 1

3

3

5

1073

Sample Output 1

4

6

92

Answer 1

#include <iostream>


using namespace std;
void func(){
    int K;
    cin >> K;
    int c=2, v=1;


    K-=1;
    while(K >= v){
        K -= v;
        c += 2;
        v++;
    }


    cout << c << endl;
}






int main(){
    int f1;
    int f2;
    int t=1;
    cin >> t;


    while(t--){
        func();
    }
}