小 Q 正在玩一款 RPG 游戏。在这个游戏中，武器可以进行升级。初始时，武器等级为 0，等级上限为 $n$。假设当前等级为 $i$ ($0 \le i < n$)，小 Q 可以花费 $c_i$ 枚金币来升级武器，升级后，武器等级有 $p_i$ 的概率变为 $i+1$，有 $(1 - p_i) \frac{w_j}{\sum_{k=1}^i w_k}$ 的概率变为 $i-j$ ($1 \le j \le i$)。

尽管小 Q 非常富有，但他仍然想知道将武器从等级 0 升级到等级 $n$ 所需的金币期望值。请编写一个程序来帮助他。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 300$)，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示等级上限。 接下来的 $n$ 行中，第 $i$ 行 ($1 \le i \le n$) 包含两个整数 $P_{i-1}$ 和 $c_{i-1}$ ($1 \le P_{i-1}, c_{i-1} \le 100$)，描述等级 $i-1$ 的成功概率和花费。这里 $p_{i-1} = \frac{P_{i-1}}{100}$。保证 $P_0 = 100$。 下一行包含 $n-1$ 个整数 $w_1, w_2, \dots, w_{n-1}$ ($1 \le w_i \le 100$)。 保证所有 $n$ 的总和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示升级到等级 $n$ 所需金币的期望值。 更准确地说，如果答案为 $\frac{p}{q}$，你应该输出满足 $q \cdot r \equiv p \pmod{998\,244\,353}$ 的最小非负整数 $r$。你可以放心地假设在所有测试用例中这样的 $r$ 总是存在的。

样例

输入 1

2
2
100 1
50 5
1
3
100 1
70 2
50 3
2 3

输出 1

12
228170152