Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 109    Accepted Submission(s): 48

Problem Description

Our lovely KK has a difficult mathematical problem:he has a
N(1≤N≤1018)
meters steel,he will cut it into steels as many as possible,and he doesn't want any two of them be the same length or any three of them can form a triangle.

 

Input

The first line of the input file contains an integer
T(1≤T≤10),
which indicates the number of test cases.



Each test case contains one line including a integer
N(1≤N≤1018),indicating
the length of the steel.

 

Output

For each test case, output one line, an integer represent the maxiumum number of steels he can cut it into.

 

Sample Input

1

6

 

Sample Output

3

Hint

1+2+3=6 but 1+2=3  They are all different and cannot make a triangle.

 

 

Source

 

Recommend

hujie   |   We have carefully selected several similar problems for you:  5624 5623 5622 5621 5619

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

__int64 f[1000];

__int64 n;

int main()

{

	int t;

	scanf("%d",&t);

	f[0]=1;

	f[1]=1;

	for(int i=2;i<=100;i++)

	f[i]=f[i-1]+f[i-2];

	while(t--)

	{

		cin>>n;

		__int64 ans=1;

		while(n)

		{

			n-=f[ans];

//			printf("%d %d\n",n,f[ans]);

			if(n<f[ans+1]) break;

			ans++;

		}

		cout<<ans<<endl;

	}

	return 0;

}