学步园

#include <iostream>
#include <cmath>
using namespace std;


int64_t fibo[]={
 0, 1, 2, 3, 5, 8,
13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368,
75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976,
7778742049};
int fiblen = sizeof(fibo) / sizeof(fibo[0]);

int main()
{
	int t ;
	cin >> t ;
	while(t--)
	{
		long long int n ;
		cin >> n ;
		int begin = 0 ;
		int end = fiblen-1 ;
		int mid ;
		bool flag = false ;
		while(begin <= end )
		{
			 mid = (begin + end )/2;
			if(fibo[mid]  < n)  begin = mid + 1 ;
			else if (fibo[mid] >n) end = mid -1 ;
			else 
			{
			
				cout << "IsFibo" << endl ;
				flag = true ;
				break;
			}
			
		}
	    if (!flag ) cout << "IsNotFibo" << endl;
	
	}
}