题目背景

USTCPC 设置 2s 时限为了使得 python 通过。洛谷改为 1s 时限。

题目描述

克露丝卡尔酱喜欢 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，否则输出对应答案。

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$ 的情形。