You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

克露丝卡尔酱喜欢 os！（o 代表圆，通原，s 代表神），里面有一位名叫凝光的角色。

璃月的天权星凝光大人最热衷的就是赚取摩拉。

近日她研究出了一种生财之道。如果她能在第一天赚 $p$ 个摩拉，就能在第二天赚 $p+1$ 个摩拉，并从第三天开始，每天所赚的摩拉是前两天赚的摩拉之和。

现在凝光想知道，按照这种赚钱方法，如果在第 $a$ 天赚到了 $x$ 个摩拉，那么在第 $b$ 天能赚多少摩拉？

输入格式

输入第一行表示数据组数 $T$ $(1 \leq T\leq 10^5)$。

接下来 $T$ 行，每行三个整数 $a,x,b$ $(1 \leq a,b \leq 20$，$1 \leq x \leq 10 ^ {10})$。

数据保证如果答案存在，那么 $1 \leq p \leq 10^6$，保证输入均为整数。

输出格式

输出对应输入，每行一个整数，若不存在第 $a$ 天赚 $x$ 摩拉的情况，则输出 -1，否则输出对应答案。

样例 #1

样例输入 #1

3
1 1 2
3 5 4
3 4 6

样例输出 #1

2
8
-1

提示

对于 3 5 4 的情况，第一天 $p=2$ ，第二天 $3$，第三天 $5$，第四天 $8$。

对于 3 4 6 的情况，不存在使得第三天 $4$ 的情形。