9999014 - 因子和

给出a,b，求出a^b的因子和对998,244,353取模的结果。

第一行一个数t，表示数据组数。

接下来t行，每行两个数a,b，用一个空格隔开，代表一组数据。

对于每组数据，分行输出答案。

对于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。