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.

#### Sample Input

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