杰哥又遇到了一个问题： 给你两个数列 $\{A\},\{B\}$，长度都为 $H$，试求 ${A_1}^{B_1}+{A_2}^{B_2}+{A_3}^{B_3}+\dots+{A_H}^{B_H}\bmod M$ 的值。 当然，作为学霸，杰哥不是不会做，而是太懒了。于是他又向聪明的程序员——你来求助了。请帮他**快速**算出该表达式的值。

第一行包含一个整数 $T\ (T\le 100)$，表示测试数据组数。 每组数据第一行包含一个整数 $M\ (1\le M\le 32768)$，第二行包含一个整数 $H\ (1\le H\le 32768)$，其后 $H$ 行每行包含两个整数 $A_i,B_i\ (1\le A_i,B_i\le 32768)$。

对于每组数据，在一行内输出表达式的值。

快速幂

POJ1995