You are given an integer, $N$. Write a program to determine if $N$ is an element of the Fibonacci sequence.  

The first few elements of the Fibonacci sequence are $0,1,1,2,3,5,8,13,\cdots$. 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}$. 

Formally: 

$\begin{aligned}&\textit{fib}_0=0\\ &\textit{fib}_1=1\\ &\vdots\\ &\textit{fib}_n=fib_{n-1}+fib_{n-2}\forall n>1\end{aligned}$

Function Description   

Complete the isFibo function in the editor below.   

isFibo has the following parameters: 

- int n: the number to check   

Returns 

- string: either IsFibo or IsNotFibo

Input Format 

The first line contains ${t}}$, number of test cases. 

${t}}$ lines follow. Each line contains an integer $n$.

Constraints 

$1\leq t\leq10^5$ 

$1\leq n\leq10^{10}$

Sample Input  

STDIN   Function
-----   --------
3       t = 3
5       n = 5
7       n = 7
8       n = 8

Sample Output  

IsFibo
IsNotFibo
IsFibo

Explanation 

$5$ is a Fibonacci number given by ${fib}_5=3+2$ 

$7$ is not a Fibonacci number 

$8$ is a Fibonacci number given by ${fib}_6=5+3$  

Time Limit 

The time limit for this challenge is given here.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
import sys
T = int(sys.stdin.readline())
fibonacci = [1, 1]
while fibonacci[-1] <= 10 ** 10:
	fibonacci.append(fibonacci[-1] + fibonacci[-2])
for _ in range(T):
	N = int(sys.stdin.readline())
	print('IsFibo' if N in fibonacci else 'IsNotFibo')


import sys

def is_fibo(N):
	if N == 1:
		return True
	else:
		fibo1 = 0
		fibo2 = 1
		cur = 1
		while cur <= N:
			if cur == N:
				return True
			else:
				fibo1 = fibo2
				fibo2 = cur
				cur = fibo1 + fibo2
		return False
T = int(sys.stdin.readline())
for i in range(0, T):
	n = int(sys.stdin.readline())
	if is_fibo(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


def isFibo(n, a, b):
	if n == a or n == b:
		return True
	elif n < b:
		return False
	else:
		return isFibo(n, b, a + b)

def main():
	numTests = input()
	for i in range(0, int(numTests)):
		n = input()
		if isFibo(int(n), 0, 1):
			print('IsFibo')
		else:
			print('IsNotFibo')
main()


import sys
import math
a = 0

def isPerfectSquare(n):
	s = int(math.sqrt(n))
	return s * s == n

def isFibo(n):
	return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)
for l in sys.stdin:
	if a == 0:
		a = a + 1
		continue
	elif isFibo(int(l)):
		print('IsFibo')
	else:
		print('IsNotFibo')


fibos = [1, 1]
while sum(fibos[-2:]) <= 10 ** 10:
	fibos.append(sum(fibos[-2:]))
t = int(input())
while t > 0:
	n = int(input())
	if n in fibos:
		print('IsFibo')
	else:
		print('IsNotFibo')
	t -= 1


def fibs(start, end):
	if start[-2] >= end:
		return start
	start.append(start[-1] + start[-2])
	return fibs(start, end)
T = int(input())
m = 1
fib = [0, 1]
for i in range(0, T):
	N = int(input())
	if N > m:
		fib = fibs(fib, N)
		m = N
	if N in fib:
		print('IsFibo')
	else:
		print('IsNotFibo')


def main():
	T = int(input())
	N = []
	for i in range(T):
		N.append(int(input()))
	FIBS = fibs()
	for i in N:
		if i in FIBS:
			print('IsFibo')
		else:
			print('IsNotFibo')

def fibs():
	l = [0, 1]
	while l[-1] < 10 ** 10:
		l.append(l[-1] + l[-2])
	return set(l)
main()


import math

def isFib(x):
	if math.sqrt(5 * x * x + 4) % 1 == 0 or math.sqrt(5 * x * x - 4) % 1 == 0:
		return 'IsFibo'
	else:
		return 'IsNotFibo'
n = int(input())
for i in range(0, n):
	q = int(input())
	print(isFib(q))


def isFibo(nlist):
	f = [0, 1, 1, 2]
	m = max(nlist)
	while f[-1] <= m:
		f.append(f[-1] + f[-2])
	f = set(f)
	for n in nlist:
		if n in f:
			print('IsFibo')
		else:
			print('IsNotFibo')
T = int(input())
nlist = []
for i in range(T):
	nlist.append(int(input()))
isFibo(nlist)


import fileinput

def fib_generator():
	fibs = [0, 1]

	def fibs_to_n(n):
		nonlocal fibs
		while fibs[-1] < n:
			fibs += [fibs[-2] + fibs[-1]]
		return fibs
	return fibs_to_n
fibs_to_n = fib_generator()

def is_fib(num):
	fibs = fibs_to_n(num)
	return num in fibs
is_first = True
for line in fileinput.input():
	if is_first:
		is_first = False
		continue
	if is_fib(int(line)):
		print('IsFibo')
	else:
		print('IsNotFibo')


fibs = [0, 1]

def is_fib(n):
	while n > fibs[-1]:
		fibs.append(fibs[-1] + fibs[-2])
	return n in fibs
t = int(input())
for c in range(t):
	if is_fib(int(input())):
		print('IsFibo')
	else:
		print('IsNotFibo')


cases = int(input())
for _ in range(cases):
	num = int(input())
	if num == 0 or num == 1:
		print('IsFibo')
	else:
		first = 0
		second = 1
		while second < num:
			temp = first
			first = second
			second = second + temp
		if second == num:
			print('IsFibo')
		else:
			print('IsNotFibo')


import sys
import math
from decimal import Decimal
high = 50
low = 0
a = Decimal('0.5') + Decimal('1.25').sqrt()
b = Decimal('0.5') - Decimal('1.25').sqrt()

def f(n):
	return int(((a ** n - b ** n) / Decimal('5').sqrt()).to_integral_exact())
T = int(sys.stdin.readline())
fibs = [f(n) for n in range(0, 60)]
for i in range(0, T):
	n = int(sys.stdin.readline())
	if n in fibs:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def is_fibonacci(n):
	phi = 0.5 + 0.5 * math.sqrt(5.0)
	a = phi * n
	return n == 0 or abs(round(a) - a) < 1.0 / n
t = int(input())
for i in range(t):
	if is_fibonacci(int(input())):
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
import bisect
fiblist = [0, 1, 1, 2, 3, 5]

def fib(n):
	if n < len(fiblist):
		return fiblist[n]
	else:
		val = fib(n - 2) + fib(n - 1)
		fiblist.append(val)
		return val

def resolve(n):
	while True:
		if n < fiblist[len(fiblist) - 1]:
			break
		else:
			fib(len(fiblist))
	i = bisect.bisect_left(fiblist, n)
	if i != len(fiblist) and fiblist[i] == n:
		return 'IsFibo'
	else:
		return 'IsNotFibo'
r = sys.stdin.readline
line = r()
testnum = int(line)
for i in range(testnum):
	n = int(r())
	print(resolve(n))


def isAFibNumber(num):
	if num == 1 or num == 0:
		return 1
	result = 0
	terms = [0, 1]
	i = 2
	while num > terms[i - 1]:
		terms.append(terms[i - 1] + terms[i - 2])
		if terms[i] == num:
			result = 1
		i = i + 1
	return result
inputNums = []
numInputs = int(input())
i = 0
while i < numInputs:
	inputNums.append(int(input()))
	i = i + 1
for num in inputNums:
	isFib = isAFibNumber(num)
	if isFib == 1:
		print('IsFibo')
	else:
		print('IsNotFibo')


from math import sqrt, floor, log
golden_ratio = (1 + sqrt(5)) / 2

def fibonacci_index(F):
	N = floor(log(F * sqrt(5) + 0.5) / log(golden_ratio))
	return int(N)

def fibonacci(N):
	F = floor(golden_ratio ** N / sqrt(5) + 0.5)
	return int(F)

def isFibbonacci(F):
	return fibonacci(fibonacci_index(F)) == F
n = int(input())
for i in range(n):
	f = int(input())
	if isFibbonacci(f):
		print('IsFibo')
	else:
		print('IsNotFibo')


max_num = 10000000000
a = 0
b = 1
fib_seq = [0, 1]
while b < max_num:
	fib_sum = a + b
	a = b
	b = fib_sum
	fib_seq.append(fib_sum)
t = input()
for i in range(int(t)):
	num = input()
	if int(num) in fib_seq:
		print('IsFibo')
	else:
		print('IsNotFibo')


N = int(input())
ls = [0, 1]
maxIn = 1
for i in range(N):
	currNum = int(input())
	if currNum < 0:
		print('IsNotFibo')
		continue
	if currNum == 0 or currNum == 1:
		print('IsFibo')
		continue
	if currNum in ls:
		print('IsFibo')
		continue
	elif ls[len(ls) - 1] > currNum:
		print('IsNotFibo')
		continue
	currFib = ls[len(ls) - 1]
	while currNum > currFib:
		currFib = ls[len(ls) - 1] + ls[len(ls) - 2]
		ls.append(currFib)
		if currNum == currFib:
			print('IsFibo')
			break
		elif currNum < currFib:
			print('IsNotFibo')
			break


from sys import stdin
(a, b) = (0, 1)
fibos = {0}
while b < 10 ** 10:
	fibos.add(b)
	(a, b) = (b, b + a)
T = int(stdin.readline())
for _ in range(T):
	N = int(stdin.readline())
	if N in fibos:
		print('IsFibo')
	else:
		print('IsNotFibo')


s = [0, 1]
i = 2
while s[i - 1] < 10000000000:
	b = s[i - 1] + s[i - 2]
	s.append(b)
	i = i + 1
t = int(input())
for i in range(0, t):
	n = int(input())
	if n in s:
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
cases = int(sys.stdin.readline())

def fibonnaci(x):
	(previous, current) = (0, 1)
	while x > previous:
		(previous, current) = (current, previous + current)
	if x == previous:
		return sys.stdout.write('IsFibo' + '\n')
	else:
		return sys.stdout.write('IsNotFibo' + '\n')
for case in range(cases):
	fibonnaci(int(sys.stdin.readline()))


import math
import sys
T = int(input())
while T > 0:
	N = int(input())
	a = math.sqrt(5 * N * N + 4)
	b = math.sqrt(5 * N * N - 4)
	if float(a).is_integer() or float(b).is_integer():
		print('IsFibo')
	else:
		print('IsNotFibo')
	T = T - 1


import math

def isPerfectSquare(x):
	s = int(math.sqrt(x))
	return s * s == x

def isFib(n):
	return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)
t = int(input())
for i in range(t):
	n = int(input())
	b = isFib(n)
	if b:
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
number = ''
numbers = []
fibo = set()
max = 0
x = 0
y = 1
i = 0
for line in sys.stdin:
	numbers.append(int(line))
	if max < int(line):
		max = int(line)
while i < max + 1:
	i = x + y
	x = y
	y = i
	fibo.add(i)
for number in numbers[1:]:
	if number in fibo:
		print('IsFibo')
	else:
		print('IsNotFibo')


def fibo(n):
	res = []
	a = 0
	b = 1
	res.append(a)
	res.append(b)
	for i in range(1000):
		c = a + b
		a = b
		b = c
		if c < n:
			res.append(c)
		else:
			break
	return res
res = fibo(10 ** 10)
t = int(input())
for i in range(t):
	n = int(input())
	IsFibo = False
	for e in res:
		if e == n:
			IsFibo = True
			print('IsFibo')
			break
	if not IsFibo:
		print('IsNotFibo')


__author__ = 'mnganesh'
from bisect import bisect_left

class Fibonacci:

	def __init__(self):
		self.__series = [0, 1]

	def isFibo(self, number):
		if self.__series[-1] < number:
			return self.__fillSeries(number) == number
		else:
			hi = len(self.__series)
			pos = bisect_left(self.__series, number)
			return True if pos != hi and self.__series[pos] == number else False

	def __fillSeries(self, limit):
		nextFiboNumber = self.__series[-1]
		while nextFiboNumber < limit:
			nextFiboNumber = self.__series[-1] + self.__series[-2]
			self.__series.append(nextFiboNumber)
		return nextFiboNumber

	def __str__(self):
		return str(self.__series)
nCases = int(input())
fiboSeries = Fibonacci()
for i in range(nCases):
	number = int(input())
	if fiboSeries.isFibo(number):
		print('IsFibo')
	else:
		print('IsNotFibo')


from math import *

def perfectSquare(n):
	return int(sqrt(n)) ** 2 == n
n = int(input())
for i in range(n):
	k = int(input())
	k = 5 * k ** 2
	if perfectSquare(k + 4) or perfectSquare(k - 4):
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
fibs = [0, 1, 1]
test_cases = []
x = [int(i.strip()) for i in sys.stdin.readlines()[1:]]

def test_fib(n):
	if fibs[-1] < n:
		while fibs[-1] < n:
			fibs.append(fibs[-1] + fibs[-2])
	if n in fibs:
		return True
	else:
		return False
for i in x:
	if test_fib(i):
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
from math import *
t = int(input())
for i in range(t):
	n = int(input())
	n = 5 * n ** 2
	one = n + 4
	two = n - 4
	sqrtone = int(sqrt(one))
	sqrttwo = int(sqrt(two))
	if sqrtone * sqrtone == one or sqrttwo * sqrttwo == two:
		print('IsFibo')
	else:
		print('IsNotFibo')


import fileinput

def is_fib(n):
	if n < 4:
		return 'IsFibo'
	f0 = 2
	f1 = 3
	while f1 < n:
		temp = f1
		f1 = f0 + f1
		f0 = temp
	if f1 == n:
		return 'IsFibo'
	else:
		return 'IsNotFibo'
for line in fileinput.input():
	if not fileinput.isfirstline():
		print(is_fib(int(line)))


import sys
fiboNums = [0, 1]

def expandFiboNums():
	fiboNums.append(fiboNums[-2] + fiboNums[-1])

def isFibo(n):
	while fiboNums[-1] < n:
		expandFiboNums()
	return n in fiboNums

def readNum():
	return int(sys.stdin.readline())
for line in range(readNum()):
	if isFibo(readNum()):
		print('IsFibo')
	else:
		print('IsNotFibo')


T = int(input())

class Fib:

	def __init__(self):
		self.calc_nums = set([0, 1])
		self.previous = 0
		self.current = 1

	def contains(self, n):
		if n in self.calc_nums:
			return True
		elif self.current > n:
			return False
		else:
			while self.current < n:
				(self.current, self.previous) = (self.current + self.previous, self.current)
				self.calc_nums.add(self.current)
			if self.current == n:
				return True
			return False
fib = Fib()
for _ in range(T):
	N = int(input())
	if fib.contains(N):
		print('IsFibo')
	else:
		print('IsNotFibo')


def binSearch(val, minR, maxR, func):
	if minR > maxR:
		return -1
	mid = int((minR + maxR) / 2)
	funcVal = func(mid)
	if funcVal == val:
		return mid
	elif funcVal > val:
		maxR = mid - 1
	else:
		minR = mid + 1
	return binSearch(val, minR, maxR, func)
fib = [0] * 51
fib[1] = 1
for i in range(2, 51):
	fib[i] = fib[i - 2] + fib[i - 1]

def fibN(index):
	return fib[index]
t = int(input())
for i in range(t):
	output = 'IsNotFibo' if binSearch(int(input()), 0, 50, fibN) == -1 else 'IsFibo'
	print(output)


def next_fibo():
	a = 0
	b = 1
	while True:
		yield a
		c = a + b
		(a, b) = (b, c)
T = int(input())
for j in range(T):
	n = int(input())
	for i in next_fibo():
		if i == n:
			print('IsFibo')
			break
		elif i > n:
			print('IsNotFibo')
			break


t = int(input())
f = 0
s = 1
b = 0
while t > 0:
	a = int(input())
	if a == 0:
		print('IsFibo')
		t = t - 1
		continue
	if a == 1:
		print('IsFibo')
		t = t - 1
		continue
	f = 0
	s = 1
	b = 0
	while b < a:
		b = f + s
		f = s
		s = b
		if b == a:
			print('IsFibo')
			break
	if b != a:
		print('IsNotFibo')
	t = t - 1


def is_fibonacci(n):
	phi = 0.5 + 0.5 * 2.23606797749979
	a = phi * n
	return n == 0 or abs(round(a) - a) < 1.0 / n
import sys
import cmath
t = int(input())
for i in range(t):
	n = int(input())
	if is_fibonacci(n):
		sys.stdout.write('IsFibo\n')
		sys.stdout.flush()
	else:
		sys.stdout.write('IsNotFibo\n')
		sys.stdout.flush()


import sys
import math
check = 0
inputlist = []

def isFibo(a):
	delta = 0.5 + 0.5 * math.sqrt(5.0)
	n = delta * a
	if a == 0 or abs(round(n) - n) < 1.0 / a:
		print('IsFibo')
	else:
		print('IsNotFibo')
for line in sys.stdin:
	for i in line.split():
		if check == 0:
			n = int(i)
			check = 1
		else:
			inputlist.append(int(i))
for a in inputlist:
	isFibo(a)


a = input()
a = int(a)
for x in range(0, a):
	b = int(input())
	x = 0
	y = 1
	z = 1
	p = 2
	while y < b:
		z = x + y
		x = y
		y = z
		p = p + 1
	if y == b or x == b:
		print('IsFibo')
	else:
		print('IsNotFibo')


def fib(n, curr, prev):
	if n == 1:
		return curr
	else:
		new_curr = curr + prev
		return fib(n - 1, new_curr, curr)
my_no = 0
fib_list = []
n = 1
while my_no < 10 ** 10:
	fib_list.append(my_no)
	my_no = fib(n, 1, 0)
	n += 1
t = int(input())
while t > 0:
	no = int(input())
	if no in fib_list:
		print('IsFibo')
	else:
		print('IsNotFibo')
	t -= 1


import math
import math
t = input()
l = []
for i in range(0, int(t)):
	n = input()
	l.append(int(n))
for i in l:
	m = math.sqrt(5 * (i * i) + 4)
	j = math.sqrt(5 * (i * i) - 4)
	if math.floor(m) != m and math.floor(j) != j:
		print('IsNotFibo')
	else:
		print('IsFibo')


import math
t = int(input())
while t > 0:
	n = int(input())
	i = 0
	r = 0
	ans = 0
	if n == 0:
		ans = 1
	while r < n:
		a = 1 + math.sqrt(5)
		b = 1 - math.sqrt(5)
		p = math.pow(a, i) - math.pow(b, i)
		q = math.pow(2, i) * math.sqrt(5)
		r = int(p / q)
		i = i + 1
		if r == n:
			ans = 1
			break
	if ans == 1:
		print('IsFibo')
	else:
		print('IsNotFibo')
	t = t - 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = 5 * n ** 2 + 4
	b = 5 * n ** 2 - 4
	c = int(math.sqrt(a))
	d = int(math.sqrt(b))
	if c * c == a or d * d == b:
		print('IsFibo')
	else:
		print('IsNotFibo')


from math import sqrt

def isSq(n):
	sqn = int(sqrt(n))
	return sqn * sqn == n

def isFibo(n):
	return isSq(5 * n * n + 4) | isSq(5 * n * n - 4)
for case in range(int(input())):
	print('IsFibo' if isFibo(int(input())) else 'IsNotFibo')


import math
PHI = (1 + math.sqrt(5)) / 2

def n(F):
	return int(math.floor(math.log(F * math.sqrt(5) + 0.5, PHI)))

def F(n):
	return int(round(PHI ** n / math.sqrt(5)))
T = int(input())
for i in range(T):
	N = int(input())
	n_ = n(N)
	print('IsFibo' if N == F(n_) else 'IsNotFibo')


from math import sqrt
x = int(input())
for i in range(x):
	num = int(input())
	z = 5 * num * num - 4
	y = z + 8
	sz = sqrt(z)
	if sz - sz // 1 < 1e-20:
		print('IsFibo')
		continue
	sy = sqrt(y)
	if sy - sy // 1 < 1e-17:
		print('IsFibo')
		continue
	print('IsNotFibo')


def main():
	test_num = int(input())
	fib_inputs = [int(input()) for n in range(test_num)]
	max_fib = max(fib_inputs)
	init_fib = [0, 1]
	(a, b) = init_fib
	fib_set = set(init_fib)
	while b < max_fib:
		(a, b) = (b, a + b)
		fib_set.add(b)
	for f in fib_inputs:
		if f in fib_set:
			print('IsFibo')
		else:
			print('IsNotFibo')
main()


import math
x = int(input())
for i in range(0, x):
	a = int(input())
	b = math.sqrt(5 * a * a + 4)
	c = math.sqrt(5 * a * a - 4)
	if int(b) == b:
		print('IsFibo')
	elif int(c) == c:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def is_fibonacci(n):
	phi = 0.5 + 0.5 * math.sqrt(5.0)
	a = phi * n
	return n == 0 or abs(round(a) - a) < 1.0 / n
t = int(input())
for k in range(0, t):
	n = int(input())
	if is_fibonacci(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys

def isFibo():
	inpt = sys.stdin
	case_num = int(inpt.readline())
	for i in range(case_num):
		case = int(inpt.readline())
		left = 5 * case * case - 4
		right = 5 * case * case + 4
		isFibo = False
		for j in [left, right]:
			l = 1
			r = j
			while 1:
				center = int((l + r) / 2)
				if center * center == j or (center - 1) * (center - 1) == j:
					isFibo = True
					break
				if center * center > j and (center - 1) * (center - 1) > j:
					r = center
					continue
				if center * center < j and (center - 1) * (center - 1) < j:
					l = center
					continue
				if center * center > j and (center - 1) * (center - 1) < j:
					break
			if isFibo:
				print('IsFibo')
				break
		if not isFibo:
			print('IsNotFibo')
isFibo()


import math
t = int(input())
while t > 0:
	t = t - 1
	x = int(input())
	a = 5 * x * x + 4
	b = 5 * x * x - 4
	p = int(math.sqrt(a))
	q = int(math.sqrt(b))
	if p * p == a or q * q == b:
		print('IsFibo')
	else:
		print('IsNotFibo')


def isFibo(k):
	f0 = 0
	f1 = 1
	while f0 <= k:
		if f0 == k:
			return print('IsFibo')
		else:
			(f0, f1) = (f1, f0 + f1)
	print('IsNotFibo')
n = int(input())
for i in range(n):
	isFibo(int(input()))


import sys
array = []
a = 1
b = 1
c = 2
array.append(a)
array.append(b)
array.append(c)
T = int(input())
for i in range(1, sys.maxsize):
	a = b
	b = c
	c = a + b
	array.append(c)
	if len(str(c)) == 12:
		break
for i in range(T):
	x = int(input())
	if x in array:
		print('IsFibo')
	else:
		print('IsNotFibo')


def isFibo(x):
	result = 0
	old_result = 1
	while result < x:
		(result, old_result) = (old_result, result)
		result += old_result
		if result == x:
			return 1
	else:
		return 0
number_of_cases = int(input())
for i in range(number_of_cases):
	x = int(input())
	if isFibo(x):
		print('IsFibo')
	else:
		print('IsNotFibo')


fibos = {1: True, 2: True}
f1 = 1
f2 = 2
while True:
	f3 = f1 + f2
	fibos[f3] = True
	if f3 > 10000000000:
		break
	f1 = f2
	f2 = f3
t_count = int(input())
while t_count > 0:
	if fibos.get(int(input())):
		print('IsFibo')
	else:
		print('IsNotFibo')
	t_count -= 1


import math

def isPerfectSquare(t):
	sq = math.sqrt(t)
	return int(sq) == sq
count = int(input())
for i in range(count):
	n = int(input())
	t1 = 5 * n * n + 4
	t2 = 5 * n * n - 4
	if isPerfectSquare(t1) or isPerfectSquare(t2):
		print('IsFibo')
		continue
	print('IsNotFibo')


t = int(input())
for i in range(0, t):
	x = int(input())
	if (5 * x ** 2 + 4) ** 0.5 == int((5 * x ** 2 + 4) ** 0.5):
		print('IsFibo')
	elif (5 * x ** 2 - 4) ** 0.5 == int((5 * x ** 2 - 4) ** 0.5):
		print('IsFibo')
	else:
		print('IsNotFibo')


import math
n = int(input())
while n > 0:
	n = n - 1
	x = int(input())
	pos = 5 * x * x + 4
	neg = 5 * x * x - 4
	if math.sqrt(pos) == math.floor(math.sqrt(pos)):
		print('IsFibo')
	elif math.sqrt(neg) == math.floor(math.sqrt(neg)):
		print('IsFibo')
	else:
		print('IsNotFibo')


from math import sqrt

def isSq(n):
	return n == int(sqrt(n)) ** 2

def isFib(n):
	return isSq(5 * n ** 2 + 4) | isSq(5 * n ** 2 - 4)
tests = int(input())
for each in range(tests):
	n = int(input())
	if isFib(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


fibo = [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]
for t in range(int(input())):
	n = int(input())
	print('IsFibo') if n in fibo else print('IsNotFibo')


import math
t = input()

def chk(n):
	k = math.floor(math.sqrt(n))
	if k * k == n:
		return True
	return False
for i in range(int(t)):
	n = int(input())
	a = 5 * n * n + 4
	b = 5 * n * n - 4
	if chk(a) or chk(b):
		print('IsFibo')
	else:
		print('IsNotFibo')


def fib(maxfib):
	fib1 = 0
	fib2 = 1
	while fib1 < maxfib:
		(fib1, fib2) = (fib2, fib1 + fib2)
	if fib1 == maxfib:
		return True
	return False
t = int(input())
for i in range(t):
	n = int(input())
	a = fib(n)
	if a:
		print('IsFibo')
	else:
		print('IsNotFibo')


from sys import stdin
arr = [1, 2]
while arr[-1] < 10000000000:
	arr.append(arr[-1] + arr[-2])
arr = set(arr)
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	if int(inpu[i]) in arr:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def isPerfectSq(x):
	s = int(math.sqrt(x))
	return s * s == x

def isFib(n):
	return isPerfectSq(5 * n * n + 4) or isPerfectSq(5 * n * n - 4)
t = int(input())
for i in range(t):
	n = int(input())
	if isFib(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


from math import sqrt

def main():
	T = int(input())
	for i in range(T):
		n = int(input())
		ex = 5 * n * n
		e1 = is_perfect_sqr(ex + 4)
		e2 = is_perfect_sqr(ex - 4)
		if e1 or e2:
			print('IsFibo')
		else:
			print('IsNotFibo')

def is_perfect_sqr(n):
	sq_rt = int(sqrt(n))
	return sq_rt * sq_rt == n
main()


import math
t = int(input())

def psq(n):
	s = int(math.sqrt(n))
	return s * s == n
while t:
	n = int(input())
	if psq(5 * n * n + 4) or psq(5 * n * n - 4):
		print('IsFibo')
	else:
		print('IsNotFibo')
	t -= 1


def approximately_equal(a, b, precision):
	return abs(a - b) <= precision

def is_fibo(number):
	a = (5 * number ** 2 + 4) ** (1 / 2)
	b = (5 * number ** 2 - 4) ** (1 / 2)
	precision = 1e-07
	return approximately_equal(a, round(a), precision) or approximately_equal(b, round(b), precision)
T = int(input())
for i in range(T):
	number = int(input())
	print('IsFibo' if is_fibo(number) else 'IsNotFibo')


def main():
	fib = [0, 1, 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]
	T = int(input())
	for i in range(T):
		N = int(input())
		if N in fib:
			print('IsFibo')
		else:
			print('IsNotFibo')
	return 0
main()


t = input()
o = 0
while int(t) > o:
	n = int(input())
	a = 0
	b = 1
	while b <= n:
		if b == n:
			print('IsFibo')
			break
		s = b
		b = a + b
		a = s
	if b != n:
		print('IsNotFibo')
	o = o + 1


import math
testcase = int(input())
inpt = []
oupt = []
i = 0
temp = 0
demo = 0
demo1 = 0
while i < testcase:
	temp = int(input())
	inpt.append(temp)
	demo = math.sqrt(5 * (temp * temp) - 4)
	demo1 = int(demo)
	if demo == demo1:
		oupt.append(1)
	else:
		demo = math.sqrt(5 * (temp * temp) + 4)
		demo1 = int(demo)
		if demo1 == demo:
			oupt.append(1)
		else:
			oupt.append(0)
	i = i + 1
i = 0
while i < testcase:
	if oupt[i] == 1:
		print('IsFibo')
	else:
		print('IsNotFibo')
	i = i + 1


import sys

def isFibo(N):
	fibserie = []
	i = 0
	while i < N:
		if len(fibserie) < 3:
			fibserie.append(i)
			i = i + 1
		else:
			fibel = fibserie[len(fibserie) - 1] + fibserie[len(fibserie) - 2]
			fibserie.append(fibel)
			i = fibel
	if i == N:
		return 1
	else:
		return 0
lines = sys.stdin.readlines()
nlines = int(lines[0])
j = 0
while j < nlines:
	n = int(lines[j + 1])
	if isFibo(n) == 1:
		print('IsFibo')
	else:
		print('IsNotFibo')
	j = j + 1


t = int(input())
for x in range(0, t):
	n = int(input())
	a = 5 * n * n + 4
	b = 5 * n * n - 4
	p = int(pow(a, 0.5))
	q = int(pow(a, 0.5))
	if p * p == a or q * q == b:
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
import math

def isSquare(a):
	if a < 0:
		return False
	else:
		temp = int(math.sqrt(a))
	return temp * temp == a

def isFibo(N):
	N = int(N)
	if isSquare(5 * N * N + 4) or isSquare(5 * N * N - 4):
		print('IsFibo')
		return
	else:
		print('IsNotFibo')
		return

def main():
	count = sys.stdin.readline()
	list = []
	line = sys.stdin.readline()
	while line != '':
		list.append(line)
		line = sys.stdin.readline()
	for n in list:
		isFibo(n)
main()


fibs = [0, 1]
l = 2
fib = 0
while fib < 100000000000.0:
	fib = fibs[l - 2] + fibs[l - 1]
	fibs.append(fib)
	l += 1
t = int(input())
for i in range(t):
	n = int(input())
	if n in fibs:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def sq(n):
	if n >= 0:
		s = math.floor(math.sqrt(n))
		if s * s == n:
			return True
		else:
			return False
	else:
		return False
k = int(input())
while k > 0:
	n = int(input())
	if sq(5 * n * n + 4) or sq(5 * n * n - 4):
		print('IsFibo')
	else:
		print('IsNotFibo')
	k = k - 1


import sys
T = int(sys.stdin.readline())
fibos = set([0, 1])
(prev_prev, prev) = (0, 1)
while prev <= 10000000000:
	(prev_prev, prev) = (prev, prev_prev + prev)
	fibos.add(prev)
for t in range(T):
	N = int(sys.stdin.readline())
	if N in fibos:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def is_fib(n):
	phi = 0.5 + 0.5 * math.sqrt(5.0)
	a = phi * n
	return n == 0 or abs(round(a) - a) < 1.0 / n
t = int(input())
while t > 0:
	n = int(input())
	if is_fib(n):
		print('IsFibo')
	else:
		print('IsNotFibo')
	t -= 1


import sys
data = sys.stdin.readlines()
fib0 = 0
fib1 = 1
numbers = [0, 1]
while fib1 < 10 ** 10:
	n = fib0 + fib1
	fib0 = fib1
	fib1 = n
	numbers += [fib1]
for n in range(1, len(data)):
	print('IsFibo' if int(data[n]) in numbers else 'IsNotFibo')


from math import floor
cases = input()

def isSquare(i):
	x = i // 2
	seen = set([x])
	try:
		while x * x != i:
			x = (x + i // x) // 2
			if x in seen:
				return False
			seen.add(x)
	except:
		return False
	return True

def isFibo(i):
	return isSquare(5 * i ** 2 - 4) or isSquare(5 * i ** 2 + 4)
for i in range(int(cases)):
	print('IsFibo' if isFibo(int(input())) else 'IsNotFibo')

def testFirstMillion():
	l = [1, 1, 2]
	for i in range(1000000):
		if not isFibo(l[0]):
			print('FAILED %s is a fibonnaci number but isFibo says otherwise' % l[0])
			return
		l[0] = l[1]
		l[1] = l[2]
		l[2] = l[0] + l[1]


t = int(input())
for x in range(0, t):
	n = int(input())
	a = 5 * n * n + 4
	b = 5 * n * n - 4
	p = int(pow(a, 0.5))
	q = int(pow(b, 0.5))
	if p * p == a or q * q == b:
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys

def checkFibo(num):
	(a, b) = (0, 1)
	while a <= num:
		if a == num:
			return 'IsFibo\n'
		else:
			(a, b) = (b, a + b)
		if a > num:
			return 'IsNotFibo\n'
var = sys.stdin.readline()
check = []
for i in range(int(var)):
	check.append(int(sys.stdin.readline()))
for num in check:
	sys.stdout.write(checkFibo(num))


import math

def persq(n):
	x = int(math.sqrt(n))
	if x * x == n:
		return True
	else:
		return False
t = int(input())
while t:
	t -= 1
	n = int(input())
	if persq(5 * n * n + 4) or persq(5 * n * n - 4):
		print('IsFibo')
	else:
		print('IsNotFibo')


import math
t = int(input())

def isFibo(n):
	root5 = math.sqrt(5)
	phi = (1 + root5) / 2
	idx = math.floor(math.log(n * root5) / math.log(phi) + 0.5)
	u = math.floor(math.pow(phi, idx) / root5 + 0.5)
	return u == n
while t > 0:
	t -= 1
	n = int(input())
	if isFibo(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


import sys
from bisect import bisect_left
fib = [0]
f1 = 0
f2 = 1
while f2 < sys.maxsize:
	tmp = f2 + f1
	f1 = f2
	f2 = tmp
	fib.append(f2)
n = int(input())
while n:
	f = int(input())
	pos = bisect_left(fib, f, 0, len(fib))
	print('IsFibo' if pos != len(fib) and fib[pos] == f else 'IsNotFibo')
	n -= 1


a = []
f1 = 0
f2 = 1
s = 0
a.append(f1)
a.append(f2)
for i in range(60):
	s = f1 + f2
	f1 = f2
	f2 = s
	a.append(s)
t = int(input())
for x in range(t):
	k = int(input())
	if k in a:
		print('IsFibo')
	else:
		print('IsNotFibo')


fibo = {1, 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, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176, 1500520536206896083277, 2427893228399975082453, 3928413764606871165730, 6356306993006846248183, 10284720757613717413913, 16641027750620563662096, 26925748508234281076009, 43566776258854844738105, 70492524767089125814114, 114059301025943970552219, 184551825793033096366333, 298611126818977066918552, 483162952612010163284885, 781774079430987230203437, 1264937032042997393488322, 2046711111473984623691759, 3311648143516982017180081, 5358359254990966640871840, 8670007398507948658051921, 14028366653498915298923761, 22698374052006863956975682, 36726740705505779255899443, 59425114757512643212875125, 96151855463018422468774568, 155576970220531065681649693, 251728825683549488150424261, 407305795904080553832073954, 659034621587630041982498215, 1066340417491710595814572169, 1725375039079340637797070384, 133, 7308805952221443105020355490, 11825896447871834976429068427, 19134702400093278081449423917, 30960598847965113057878492344, 50095301248058391139327916261, 81055900096023504197206408605, 131151201344081895336534324866, 212207101440105399533740733471, 343358302784187294870275058337, 555565404224292694404015791808, 898923707008479989274290850145, 1454489111232772683678306641953, 2353412818241252672952597492098, 3807901929474025356630904134051, 6161314747715278029583501626149, 9969216677189303386214405760200, 16130531424904581151, 42230279526998466217810220532898, 68330027629092351019822533679447, 110560307156090817237632754212345, 178890334785183168257455287891792, 289450641941273985495088042104137, 468340976726457153752543329995929, 757791618667731139247631372100066, 1226132595394188293000174702095995, 1983924214061919432247806074196061, 3210056809456107725247980776292056, 5193981023518027157495786850488117, 8404037832974134882743767626780173, 13598018856492162040239554477268290, 22002056689466296922983322104048463, 35600075545958458963222876581316753, 57602132235424755886206198685365216, 93202207781383214849429075266681969, 150804340016807970735635273952047185, 244006547798191185585064349218729154, 394810887814999156320699623170776339, 638817435613190341905763972389505493, 1033628323428189498226463595560281832, 1672445759041379840132227567949787325, 2706074082469569338358691163510069157, 4378519841510949178490918731459856482, 7084593923980518516849609894969925639, 11463113765491467695340528626429782121, 18547707689471986212190138521399707760, 30010821454963453907530667147829489881, 48558529144435440119720805669229197641, 78569350599398894027251472817058687522, 127127879743834334146972278486287885163, 205697230343233228174223751303346572685, 332825110087067562321196029789634457848, 538522340430300790495419781092981030533, 871347450517368352816615810882615488381, 1409869790947669143312035591975596518914, 2281217241465037496128651402858212007295, 3691087032412706639440686994833808526209, 5972304273877744135569338397692020533504, 9663391306290450775010025392525829059713, 15635695580168194910579363790217849593217, 25299086886458645685589389182743678652930, 40934782466626840596168752972961528246147, 66233869353085486281758142155705206899077, 107168651819712326877926895128666735145224, 173402521172797813159685037284371942044301, 280571172992510140037611932413038677189525, 453973694165307953197296969697410619233826, 734544867157818093234908902110449296423351, 1188518561323126046432205871807859915657177, 1923063428480944139667114773918309212080528, 3111581989804070186099320645726169127737705, 5034645418285014325766435419644478339818233, 8146227408089084511865756065370647467555938, 13180872826374098837632191485015125807374171, 21327100234463183349497947550385773274930109, 34507973060837282187130139035400899082304280, 55835073295300465536628086585786672357234389, 90343046356137747723758225621187571439538669, 14617811965143821326038631213, 382699285659014174244530850035136059033084785, 619220451666590135228675387863297874269396512, 1001919737325604309473206237898433933302481297, 1621140188992194444701881625761731807571877809, 2623059926317798754175087863660165740874359106, 4244200115309993198876969489421897548446236915, 6867260041627791953052057353082063289320596021, 11111460156937785151929026842503960837766832936, 17978720198565577104981084195586024127087428957, 290901803555033622569101224, 123227981463641240980692501505442003148737643593, 199387062373213542599493807777207997205533596336, 322615043836854783580186309282650000354271239929, 522002106210068326179680117059857997559804836265, 844617150046923109759866426342507997914076076194, 1366619256256991435939546543402365995473880912459, 2211236406303914545699412969744873993387956988653, 3577855662560905981638959513147239988861837901112, 5789092068864820527338372482892113982249794889765, 9366947731425726508977331996039353971111632790877, 15156039800290547036315704478931467953361427680642, 24522987531716273545293036474970821924473060471519, 39679027332006820581608740953902289877834488152161, 64202014863723094126901777428873111802307548623680, 103881042195729914708510518382775401680142036775841, 168083057059453008835412295811648513482449585399521, 271964099255182923543922814194423915162591622175362, 440047156314635932379335110006072428645041207574883, 71201125556981885592325792420049634380763245, 1864069667454273644225850958407065116260306867075373, 3016128079338728432528443992613633888712980904400501, 4880197746793002076754294951020699004973287771475874, 7896325826131730509282250, 20672849399056463095319772838289364792345825123228624, 33449372971981195681356806732944396691005381570580873, 54122222371037658776676579571233761483351206693809497, 87571595343018854458033386304178158174356588264390370, 141693817714056513234709965875411919657707794958199867, 229265413057075367692743352179590077832064383222590237, 370959230771131880927453318055001997489772178180790104, 600224643828207248620196670234592075321836561403380341, 971183874599339129547649988289594072811608739584170445, 1571408518427546378167846658524186148133445300987550786, 2542592393026885507715496646813780220945054040571721231, 4114000911454431885883343305337966369078499341559272017, 6656593304481317393598839952151746590023553382130993248, 10770594215935749279482183257489712959102052723690265265, 17427187520417066673081023209641459549125606105821258513, 28197781736352815952563206467131172508227658829511523778, 45624969256769882625644229676772632057353264935332782291, 73822750993122698578207436143903804565580923764844306069, 119447720249892581203851665820676436622934188700177088360, 193270471243015279782059101964580241188515112465021394429, 312718191492907860985910767785256677811449301165198482789, 505988662735923140767969869749836918999964413630219877218, 818706854228831001753880637535093596811413714795418360007, 1324695516964754142521850507284930515811378128425638237225, 2143402371193585144275731144820024112622791843221056597232, 3468097888158339286797581652104954628434169971646694834457, 5611500259351924431073312796924978741056961814867751431689, 9079598147510263717870894449029933369491131786514446266146, 14691098406862188148944207245954912110548093601382197697835, 23770696554372451866815101694984845480039225387896643963981}
for _ in range(int(input())):
	if int(input()) in fibo:
		print('IsFibo')
	else:
		print('IsNotFibo')


fibo = {1, 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, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176, 1500520536206896083277, 2427893228399975082453, 3928413764606871165730, 6356306993006846248183, 10284720757613717413913, 16641027750620563662096, 26925748508234281076009, 43566776258854844738105, 70492524767089125814114, 114059301025943970552219, 184551825793033096366333, 298611126818977066918552, 483162952612010163284885, 781774079430987230203437, 1264937032042997393488322, 2046711111473984623691759, 3311648143516982017180081, 5358359254990966640871840, 8670007398507948658051921, 14028366653498915298923761, 22698374052006863956975682, 36726740705505779255899443, 59425114757512643212875125, 96151855463018422468774568, 155576970220531065681649693, 251728825683549488150424261, 407305795904080553832073954, 659034621587630041982498215, 1066340417491710595814572169, 1725375039079340637797070384, 133, 7308805952221443105020355490, 11825896447871834976429068427, 19134702400093278081449423917, 30960598847965113057878492344, 50095301248058391139327916261, 81055900096023504197206408605, 131151201344081895336534324866, 212207101440105399533740733471, 343358302784187294870275058337, 555565404224292694404015791808, 898923707008479989274290850145, 1454489111232772683678306641953, 2353412818241252672952597492098, 3807901929474025356630904134051, 6161314747715278029583501626149, 9969216677189303386214405760200, 16130531424904581151, 42230279526998466217810220532898, 68330027629092351019822533679447, 110560307156090817237632754212345, 178890334785183168257455287891792, 289450641941273985495088042104137, 468340976726457153752543329995929, 757791618667731139247631372100066, 1226132595394188293000174702095995, 1983924214061919432247806074196061, 3210056809456107725247980776292056, 5193981023518027157495786850488117, 8404037832974134882743767626780173, 13598018856492162040239554477268290, 22002056689466296922983322104048463, 35600075545958458963222876581316753, 57602132235424755886206198685365216, 93202207781383214849429075266681969, 150804340016807970735635273952047185, 244006547798191185585064349218729154, 394810887814999156320699623170776339, 638817435613190341905763972389505493, 1033628323428189498226463595560281832, 1672445759041379840132227567949787325, 2706074082469569338358691163510069157, 4378519841510949178490918731459856482, 7084593923980518516849609894969925639, 11463113765491467695340528626429782121, 18547707689471986212190138521399707760, 30010821454963453907530667147829489881, 48558529144435440119720805669229197641, 78569350599398894027251472817058687522, 127127879743834334146972278486287885163, 205697230343233228174223751303346572685, 332825110087067562321196029789634457848, 538522340430300790495419781092981030533, 871347450517368352816615810882615488381, 1409869790947669143312035591975596518914, 2281217241465037496128651402858212007295, 3691087032412706639440686994833808526209, 5972304273877744135569338397692020533504, 9663391306290450775010025392525829059713, 15635695580168194910579363790217849593217, 25299086886458645685589389182743678652930, 40934782466626840596168752972961528246147, 66233869353085486281758142155705206899077, 107168651819712326877926895128666735145224, 173402521172797813159685037284371942044301, 280571172992510140037611932413038677189525, 453973694165307953197296969697410619233826, 734544867157818093234908902110449296423351, 1188518561323126046432205871807859915657177, 1923063428480944139667114773918309212080528, 3111581989804070186099320645726169127737705, 5034645418285014325766435419644478339818233, 8146227408089084511865756065370647467555938, 13180872826374098837632191485015125807374171, 21327100234463183349497947550385773274930109, 34507973060837282187130139035400899082304280, 55835073295300465536628086585786672357234389, 90343046356137747723758225621187571439538669, 14617811965143821326038631213, 382699285659014174244530850035136059033084785, 619220451666590135228675387863297874269396512, 1001919737325604309473206237898433933302481297, 1621140188992194444701881625761731807571877809, 2623059926317798754175087863660165740874359106, 4244200115309993198876969489421897548446236915, 6867260041627791953052057353082063289320596021, 11111460156937785151929026842503960837766832936, 17978720198565577104981084195586024127087428957, 290901803555033622569101224, 123227981463641240980692501505442003148737643593, 199387062373213542599493807777207997205533596336, 322615043836854783580186309282650000354271239929, 522002106210068326179680117059857997559804836265, 844617150046923109759866426342507997914076076194, 1366619256256991435939546543402365995473880912459, 2211236406303914545699412969744873993387956988653, 3577855662560905981638959513147239988861837901112, 5789092068864820527338372482892113982249794889765, 9366947731425726508977331996039353971111632790877, 15156039800290547036315704478931467953361427680642, 24522987531716273545293036474970821924473060471519, 39679027332006820581608740953902289877834488152161, 64202014863723094126901777428873111802307548623680, 103881042195729914708510518382775401680142036775841, 168083057059453008835412295811648513482449585399521, 271964099255182923543922814194423915162591622175362, 440047156314635932379335110006072428645041207574883, 71201125556981885592325792420049634380763245, 1864069667454273644225850958407065116260306867075373, 3016128079338728432528443992613633888712980904400501, 4880197746793002076754294951020699004973287771475874, 7896325826131730509282250, 20672849399056463095319772838289364792345825123228624, 33449372971981195681356806732944396691005381570580873, 54122222371037658776676579571233761483351206693809497, 87571595343018854458033386304178158174356588264390370, 141693817714056513234709965875411919657707794958199867, 229265413057075367692743352179590077832064383222590237, 370959230771131880927453318055001997489772178180790104, 600224643828207248620196670234592075321836561403380341, 971183874599339129547649988289594072811608739584170445, 1571408518427546378167846658524186148133445300987550786, 2542592393026885507715496646813780220945054040571721231, 4114000911454431885883343305337966369078499341559272017, 6656593304481317393598839952151746590023553382130993248, 10770594215935749279482183257489712959102052723690265265, 17427187520417066673081023209641459549125606105821258513, 28197781736352815952563206467131172508227658829511523778, 45624969256769882625644229676772632057353264935332782291, 73822750993122698578207436143903804565580923764844306069, 119447720249892581203851665820676436622934188700177088360, 193270471243015279782059101964580241188515112465021394429, 312718191492907860985910767785256677811449301165198482789, 505988662735923140767969869749836918999964413630219877218, 818706854228831001753880637535093596811413714795418360007, 1324695516964754142521850507284930515811378128425638237225, 2143402371193585144275731144820024112622791843221056597232, 3468097888158339286797581652104954628434169971646694834457, 5611500259351924431073312796924978741056961814867751431689}
for _ in range(int(input())):
	x = int(input())
	if x in fibo:
		print('IsFibo')
	else:
		print('IsNotFibo')


import math

def isSq(x):
	s = int(math.sqrt(x))
	return s * s == x

def isFibo(n):
	return isSq(5 * n * n + 4) or isSq(5 * n * n - 4)
t = int(input())
for i in range(t):
	n = int(input())
	if isFibo(n):
		print('IsFibo')
	else:
		print('IsNotFibo')


__author__ = 'MIrko2'
import sys
import math

def fib(n):
	while n >= len(Arr):
		Arr.append(Arr[len(Arr) - 1] + Arr[len(Arr) - 2])
	return Arr[n]

def istfib(test):
	while test > Arr[len(Arr) - 1]:
		Arr.append(Arr[len(Arr) - 1] + Arr[len(Arr) - 2])
	return test in Arr
Arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
count = int(sys.stdin.readline())
for i in range(0, count):
	testcase = int(sys.stdin.readline())
	if istfib(testcase):
		print('IsFibo')
	else:
		print('IsNotFibo')


mx = 10 ** 10
fibs = set()
(a, b) = (0, 1)
while a <= mx:
	fibs.add(a)
	(a, b) = (b, a + b)
ts = int(input())
for t in range(ts):
	n = int(input())
	if n in fibs:
		print('IsFibo')
	else:
		print('IsNotFibo')


N = 10 ** 10
F = {1}
(a, b, c) = (0, 1, 1)
while c <= N:
	(a, b) = (b, c)
	c = a + b
	F.add(c)
T = int(input())
for _ in range(T):
	N = int(input())
	if N in F:
		print('IsFibo')
	else:
		print('IsNotFibo')


t = int(input())
for _ in range(t):
	n = int(input())
	a = 0
	b = 1
	while a < n:
		(a, b) = (b, a + b)
	if a == n:
		print('IsFibo')
	else:
		print('IsNotFibo')


q = int(input())
phi = [1, 1]
for i in range(2, 100):
	phi.append(phi[i - 1] + phi[i - 2])
for w in range(q):
	n = int(input())
	print('IsFibo' if n in phi else 'IsNotFibo')


import math

def func(n):
	sq = int(math.sqrt(n))
	return bool(sq * sq == n)

def check(n):
	n1 = 5 * n * n - 4
	n2 = 5 * n * n + 4
	return bool(func(n1) or func(n2))

def main():
	t = int(input())
	for x in range(0, t):
		n = int(input())
		if check(n):
			print('IsFibo')
		else:
			print('IsNotFibo')
main()


def fibonacci():
	last = current = 0
	if not current:
		current = 1
		yield current
	while True:
		next = last + current
		last = current
		current = next
		yield current

def is_fibo(num):
	if num < 1:
		return False
	for fib in fibonacci():
		if not fib < num:
			return fib == num
OUTPUT = {True: 'IsFibo', False: 'IsNotFibo'}
count = int(input())
for _ in range(count):
	print(OUTPUT[is_fibo(int(input()))])


def binarysearch(sequence, value):
	(lo, hi) = (0, len(sequence) - 1)
	while lo <= hi:
		mid = (lo + hi) // 2
		if sequence[mid] < value:
			lo = mid + 1
		elif value < sequence[mid]:
			hi = mid - 1
		else:
			return True
	return False

def inp():
	return int(input())
first = 0
second = 1
sum = first + second
Test = inp()
l = []
l1 = []
answer = []
for i in range(Test):
	l.insert(i, inp())
for x in l:
	l1.append(x)
l.sort()
while sum < 10000000000:
	if len(l) == 0:
		break
	x = 0
	while x < len(l):
		if l[x] > sum:
			break
		elif sum > l[x]:
			del l[x]
			x -= 1
		else:
			sum == l[x]
			answer.append(l[x])
			del l[x]
			x -= 1
		x += 1
	first = second
	second = sum
	sum = first + second
for i in l1:
	if binarysearch(answer, i):
		print('IsFibo')
	else:
		print('IsNotFibo')


def is_fibonacci(m):
	phi = 0.5 + 0.5 * 2.23606797749979
	a = phi * m
	return m == 0 or abs(round(a) - a) < 1.0 / m
import sys
import cmath
x = int(input())
for i in range(x):
	m = int(input())
	if is_fibonacci(m):
		sys.stdout.write('IsFibo\n')
		sys.stdout.flush()
	else:
		sys.stdout.write('IsNotFibo\n')
		sys.stdout.flush()


from math import sqrt, log, floor, pow
rt5 = sqrt(5)
phi = (1 + rt5) * 0.5
t = int(input())
for _ in range(t):
	F = int(input())
	nF = floor(log(F * rt5 + 0.5, phi))
	Fn = floor(pow(phi, nF) / rt5 + 0.5)
	if F == Fn:
		print('IsFibo')
	else:
		print('IsNotFibo')