描述

人与人各不相同。有些人偷偷阅读充满有趣女孩照片的杂志，有些人在自家地下室鼓捣原子弹，还有人喜欢用Windows系统，而另一些人则热衷于高难度的数学游戏。最新的市场调研表明，这一市场细分领域长期以来被低估，目前市场上缺乏此类游戏。因此，这类游戏被纳入了KOKODáKH系列。游戏规则如下：

每位玩家选择两个数字 $𝐴_{i}$和$B_{i}$ ，并将它们写在一张纸条上。其他人无法看到这些数字。在某一时刻，所有玩家向其他人展示自己的数字。游戏的目标是计算所有玩家（包括自己）的 $𝐴^{B_{i}}_{i}$ 之和，并对给定的数字$𝑀$取模，确定余数。最先算出正确结果的人即为胜者。根据玩家经验，选择更大的数字可以增加游戏难度。

你需要编写一个程序来计算结果，并能够判断谁赢得了游戏。

输入

输入包含 $Z$ 个测试用例。第一行是一个正整数$Z$，表示测试用例的数量。随后是各个测试用例。每个测试用例的第一行包含一个整数 $M（1≤𝑀≤45000）$，表示模数。接下来的一行包含玩家数量$H（1≤𝐻≤45000）$。随后的 $H$ 行，每行包含两个数字 $𝐴_{i}$和$B_{i}$，用空格分隔。这两个数字不能同时为零。

输出

对于每个测试用例，输出一行，包含表达式 ($𝐴^{B_{1}}_{1}$+$𝐴^{B_{2}}_{2}$+ ... +$𝐴^{B_{H}}_{H}$) mod $M$.的结果。

输入样例

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

输出样例

2
13195
13

来源

CTU Open 1999