体力分配

题目描述

开拓者 ["舰长, 原神好玩吗"] 最近在玩新游戏 "ZZZ", 成为了一名光荣的绳匠(下称绳斤). 他注意到, "ZZZ"与其他几款游戏 ("Honkai Impact 3", "Genshin Impact", "Honkai: Star Rail") 不同, 这个游戏里面的体力消耗方式有很多方案, 所以他对体力消耗的方式按照自己的看法记录一张表：

1. 完成一次 A ,消耗 2 体力, 不限次.
2. 完成一次 B, 消耗 1 体力, 限 1 次.
3. 完成一次 C, 消耗 1 体力, 限 2 次.
4. 完成一次 D, 消耗 4体力, 不限次.
5. 完成一次 E, 消耗 1 体力, 限 3 次.
6. 完成一次 F, 消耗 1 体力, 限 1 次.
7. 完成一次 G, 消耗 3 体力, 不限次.

现在, 绳斤上线发现有 k 瓶体力药, 以及 n 点体力. 一瓶体力药水可以恢复 x 点体力. 现在他想要知道, 在拥有这么多体力的情况下, 他有多少种体力分配方案. 这个数字可能很大, 对 998244353 取模.

注意, 体力未必要用完, 比如什么都不做即消耗 0 体力也是一种方案.

数据格式

输入

第一行, 一个正整数 T. 表示测试组数.

接下来 T 行, 每行两个非负整数 n, k, x 如题意.

输出

每组测试用例一行, 输出体力分配方案的数量. 对 998244353 取模.

样例

输入

3
1 0 10
0 1 5
1 1 6

输出

5
91
204

样例解释

对于第一个测试点, 方案分别为完成[B], [C], [E], [F], [], 共5种.

数据范围及约定

$1 \le n, k, x \le 10^9.$

$T \le 10^5.$