两个函数
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

jackle 给定两个函数：
  • f(x)=ax
  • g(x)=\begin{cases} f(x)&x=1\\\sum_{i=1}^{x-1}f(f(i)) &x>1\end{cases}
他有 Q 次询问，每次给定 a,x，请你计算 g(x)\mod 998244353 的结果。

输入描述:

第一行输入 1 个正整数 Q\ (1\leq Q\leq 10^5)，表示询问次数。
接下来 Q 行，每行输入 2 个正整数 a,x\ (1\leq a,x\leq 10^9)。

输出描述:

对于每组询问，输出 g(x)\mod 998244353 的结果。
示例1

输入

复制 
3
1 1
2 2
9982 44353

输出

复制 
1
4
572321601