给出a,b，求出a^b的因子和对998,244,353取模的结果。
第一行一个数t，表示数据组数。
接下来t行，每行两个数a,b，用一个空格隔开，代表一组数据。
对于每组数据，分行输出答案。
3 9 9 8 24 43 53
581130733 49777185 225107823
对于40\%的数据，t=100。
对于另外10\%的数据，t=998244,a为质数。
对于另外20\%的数据，t=998353,a为质数的正整数次方。
对于另外10\%的数据，t=998453,b=1。
对于剩余的20\%的数据，t=10^6
对于100\%的数据，t\leq 10^6，1\leq a,b\leq 10^7。
| 时间限制 | 2 秒 |
| 内存限制 | 512 MB |