题号：NC215104
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
输入描述:
输入描述见上。
输出描述:
输出描述见上。
示例1
输入
复制
4
3 998244353
5 998244353
999999999999999999 998244353
1000000000000000000 998244353
输出
复制
30
60
801475009
801475009
