Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3702
Gibonacci number

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In mathematical terms, the normal sequence F(n) of Fibonacci numbers is defined by the recurrence relation

F(n)=F(n-1)+F(n-2)

with seed values

F(0)=1, F(1)=1

In this Gibonacci numbers problem, the sequence G(n) is defined similar

G(n)=G(n-1)+G(n-2)

with the seed value for G(0) is 1 for any case, and the seed value for G(1) is a random integer t, (t>=1). Given the i-th Gibonacci number value G(i), and the number j, your task is to output the value for G(j)

#### Input

There are multiple test cases. The first line of input is an integer T < 10000 indicating the number of test cases. Each test case contains 3 integers i, G(i) and j. 1 <= i,j <=20, G(i)<1000000

#### Output

For each test case, output the value for G(j). If there is no suitable value for t, output -1.

```4
1 1 2
3 5 4
3 4 6
12 17801 19
```

#### Sample Output

```2
8
-1
516847
```

Author: YU, Zhi
Contest: The 13th Zhejiang University Programming Contest
Submit    Status