题目描述

黑猫老师为了提升学员刷题兴趣，推出了一种奖励币。

蓝猫同学发现，如果他能在第一天赚 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})$。

数据保证如果答案存在，那么p是正整数。

输出格式

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

3
1 1 2
3 5 4
3 4 6

2
8
-1

提示

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

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