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 fibonacci sequence are 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.

Formally:

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

Input Format
The first line contains T, number of test cases.
T lines follows. Each line contains an integer N.

Output Format
Display IsFibo if N is a fibonacci number and IsNotFibo if it is not a fibonacci number. The output for each test case should be displayed on a new line.

Constraints
1 <= T <= 105
1 <= N <= 1010

Sample Input

3
5
7
8
Sample Output

IsFibo
IsNotFibo
IsFibo
The Utopian tree goes through 2 cycles of growth every year. The first growth cycle of the tree occurs during the monsoon, when it doubles in height. The second growth cycle of the tree occurs during the summer, when its height increases by 1 meter.
Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Input Format
The first line contains an integer, T, the number of test cases.
T lines follow. Each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints
1 <= T <= 10
0 <= N <= 60

Output Format
For each test case, print the height of the Utopian tree after N cycles.

Sample Input #00:

2
0
1
Sample Output #00:

1
2
Explanation #00:
There are 2 test cases. When N = 0, the height of the tree remains unchanged. When N = 1, the tree doubles its height as it's planted just before the onset of monsoon.
You are given a series, whose nth term is defined as

Tn = n2 - (n-1)2

You have to find the Sum of the series Sn = T1 + T2 + T3 + .... + Tn

Find Sn % (109 + 7)

Input Format

First line contains an integer,T, denoting the number of testcases.
Each test case contains an integer n

Output Format

For each test case, print the required sum % (109 + 7)

Constraints

1 <= T <= 10
1 <= n <= 1016

Sample Input

2
2
1
Sample Output

4
1
Explanation
Case#00 : we have 4 = 1 + 3
Case#01 : we have 1 = 1
Alex is attending a Halloween party with his girlfriend Silvia. At the party, Silvia spots a giant chocolate bar. If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Input Format
The first line contains an integer T, the number of test cases. T lines follow.
Each line contains an integer K

Output Format
T lines. Each line contains an integer that denotes the maximum number of pieces that can be obtained for each test case.

Constraints
1<=T<=10
2<=K<=107

Note
Chocolate must be served in size of 1 x 1 size pieces.
Alex can't relocate any of the pieces, nor can he place any piece on top of other.
Mark and Jane are very happy after having their first kid. Their son is very fond of toys, so Mark wants to buy some. There are N different toys lying in front of him, tagged with their prices, but he has only $K. He wants to maximize the number of toys he buys with this money.

Now, you are Mark's best friend and have to help him buy as many toys as possible.

Input Format
The first line contains two integers, N and K, followed by a line containing N space separated integers indicating the products' prices.

Output Format
An integer that denotes maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109
A toy can't be bought multiple times.

Sample Input

7 50
1 12 5 111 200 1000 10
Sample Output

4
Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.