To determine if N is an element of the Fibonacci Sequence

Given an integer, N you have to determine if N is an element of the Fibonacci Sequence.

The Fibonacci sequence looks like 0,1,1,2,3,5,8,13.... 

A Fibonacci sequence is one where every element is a sum of the previous two elements in the sequence & The first two elements are 0 and 1.
 

Method 1:
 

fib0 = 0
fib1 = 1
fibn = fibn-1 + fibn-2 ∀ n > 1
Implementation:


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
 
int perfect(long long int N)
{
     long long int sq;
     sq=sqrt(N);
     return (sq*sq == N);
}
 
int check(long long int Fi)
{
     return perfect(5*Fi*Fi+4) || perfect(5*Fi*Fi-4);
}
 
int main() 
{
     int T,status;
     long long int Fi;
     scanf("%d",&T);
     while(T>0)
     {
          scanf("%lld",&Fi);
          status=check(Fi);
          if(status==1)
          printf("IsFibo\n");
          else
          printf("IsNotFibo\n");
          T--;
     }
return 0;
}



Input Format

The first line - T, number of test cases.

T lines follows -  an integer N.

Output Format

Display IsFibo if N is a fibonacci number and IsNotFibo if it is not a fibonacci number.

Sample Input





8

Sample Output


IsFibo 
IsNotFibo 
IsFibo