象棋2

题目描述

书接上回！

自从zys大败而归, 面对棋盘自感羞愧, AI 辅助效果百倍, 学会高端开局数类, 趁着 lhy 尚未准备, 再与他奋战一回, 花拳绣腿, 那都是白给, 欲知 lhy 是否如愿败北, 不如去把公式一推！

已知 zys 对 lhy 的胜率为 p > 0.5, 他会在净胜 lhy k 场后欣喜而归, 请问两人期望下的盘数 n.

数据格式

输入

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

每个测试用例一行, 三个正整数 a, b, k. 其中p = $\frac{a}{b}$.

输出

每个测试用例一行, 一个正整数, 表示两人下的期望盘数 n 对 998244353 取模的结果.

样例

输入

2
1 1 3
10 10 4

输出

3
4

数据范围及约定

$0 < a \le b \le 10^9, k \le 10^6, \frac{a}{b} > \frac{1}{2}$