A. X-GCD
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

hushuqi 和 Liuguang_Ji 正在讨论数论问题，Liuguang_ji 随口说了一句求 $$$\gcd(a^b,b^a)$$$，其中 $$$\gcd(x,y)$$$ 表示 $$$x$$$ 与 $$$y$$$ 的最大公因数。

hushuqi 发现这个问题很简单，于是他决定把这个问题交给你。

具体地，你需要回答 $$$\gcd(a^b,b^a)$$$ 的值，这个数可能很大，你需要把答案对 $$$998244353$$$ 取模后再输出。

Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^5)$$$，表示询问次数。

接下来 $$$T$$$ 行，每行输入两个正整数 $$$a,b\ (1\le a,b\le 10^6)$$$，表示一次询问。

Output

对于每次询问，输出一行一个整数，表示答案。

Example
Input
4
12 3
5 10
114 514
91 78
Output
27
3125
304170860
306982982