AT_pakencamp_2018_day3_e 美しい和音

有一个长为 $88$ 的整数序列 $a$，其中 $a_1$ 和 $a_2$ 已给出。对于 $n\ge 3$ 的整数 $n$，$a_n=a_{n-1}+a_{n-2}$。 你需要从这 $88$ 个数中选择若干个整数，使它们在**下标不相邻**的情况下和为一个特定的整数 $x$。请求出方案数。

**本题中，单个测试点有多组测试数据。** 输入的第一行为整数 $Q$，本测试点中的数据组数。 接下来 $Q$ 行，每行三个整数 $a_1,a_2,x$。

输出 $Q$ 行，第 $i$ 行输出第 $i$ 组数据的答案。**建议在输出末尾添加换行。**

#### 数据规模与约定 **本题设有子任务。** **子任务 1（11 pts）：** $Q\le 100$，$a_1=a_2=1$，$x\le 10$。 **子任务 2（31 pts）：** $Q\le 100$，$x\le 1000\times a_2$。 **子任务 3（58 pts）：** 无特殊限制。 对于全部测试点，保证 $1\le Q\le 10^5$，$1\le a_1,a_2,x\le 10^{17}$。