You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题大样例

定义 $f(a,b,m)$ 为最小的__非负整数__ $x$ 使得其满足以下条件：

若不存在这样的 $x$，则定义 $f(a,b,m)=0$。

给定正整数 $n,a,b$，你需要求出 $\sum\limits_{i=1}^n{f(a,b,i)}$。

由于答案可能很大，所以你只需要求出对 $998244353$ 取模后的结果。

输入描述

本题一个测试点内含有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据，共一行三个正整数 $n,a,b$。

输出描述

对于每组数据，输出一行一个整数，表示 $\sum\limits_{i=1}^n{f(a,b,i)}$ 对 $998244353$ 取模后的值。

样例输入 1

5
11 45 14
19 19 810
987 654 321
19260817 2022 1130
1000000000000000000 1 1

样例输出 1

11
61
93586
58963855
716070897

样例输入 2

5
814 350 248
720249 405669 636980
492805374215689785 474 981654
663693799263468194 871 344
91063782864725724 283751 244293

样例输出 2

84407
470297443
72925427
950729984
390791696

对于 $100\%$ 的数据，保证 $1\le T\le 5,1\le n\le 10^{18},1\le a,b\le 10^6$。