期望操作数
题号:NC19467
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Nqijij 有一个数x,和一个神秘权值 q, 满足 x <= q, 每一次nqijij会随机x 变成 [x, q] 中的一个随机数,nqijij想要知道期望多少次操作之后x 变为q。
由于nqijij 是一个精力充沛的人,所以他总共会选择 T 次x 和q 进行操作,对于每一次操作,你需要输出期望多少次操作之后x 变为q 在 998244353 模意义下的值。
(令 ans = x / y, x, y 为正整数且 题目保证 x、y 与998244353 互质,则输出x * (y^(-1)), (y^(-1)) 表示y在998244353下的乘法逆元,可以证明这样的逆元存在)
题目保证 T <= 1e6, q <= 1e7, x <= 1e7;

输入描述:

第一行一个数T
接下来T行
每行两个整数 x, q (x <= q)

输出描述:

输出T行
第 i 行的正整数 表示第i次询问的答案。
示例1

输入

复制
2
7 8
15 18

输出

复制
2
831870297

说明

对于第一个样例
每一次有0.5的概率结束利用简单的求和可知是2.