# Gibonacci number

Time Limit: Java: 2000 ms / Others: 2000 ms

Memory Limit: Java: 65536 KB / Others: 65536 KB

## Description

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 indicating the number of test cases. Each test case contains 3 integers i, G(i) and j. 1 i,j G(i)

## 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

None

## Source

The 13th Zhejiang University Programming Con