只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
9999014 - 因子和
给出a,b，求出a^b的因子和对998,244,353取模的结果。
Input
第一行一个数t，表示数据组数。
接下来t行，每行两个数a,b，用一个空格隔开，代表一组数据。
Output
对于每组数据，分行输出答案。
Examples
Input
3 9 9 8 24 43 53
Output
581130733 49777185 225107823
Hint
对于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。