描述

人与人各不相同。有些人偷偷阅读满是美女图片的杂志，有些人在自家地下室里制造原子弹，有些人喜欢使用 Windows，而有些人则热衷于困难的数学游戏。最新的市场调研表明，这一市场细分领域此前被大大低估了，并且这类游戏存在短缺。因此，这种游戏被纳入 KOKODáKH 中。规则如下：

每位玩家选择两个数字 $A_i$ 和$B_i$，并将它们写在一张纸条上。其他人无法看到这些数字。在某一时刻，所有玩家向其他人展示他们的数字。目标是计算所有玩家（包括自己）的所有表达式 $A_iB_i$的总和，并确定该总和除以给定数字 $M$ 后的余数。最先计算出正确结果的人获胜。根据玩家的经验，选择更大的数字可以增加难度。

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

输入

输入包含$Z$个任务。任务的数量由输入的第一行上的单个正整数 Z 给出。随后是各个任务。每个任务以包含整数 $M（1 <= M <= 45000）$的一行开始。总和将除以这个数。下一行包含玩家数量 $H（1 <= H <= 45000）$。接下来正好有 $H$行。每行有两个数字 $A_i$和 $B_i$，用空格分隔。两个数字不能同时为零。

输出

对于每个任务，输出只有一行。在这一行上，有一个数字，即表达式

$(A_1^{B1}+A_2^{B2}+...+A_H^{BH}) mod M$

的结果。

样例输入

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

样例输出

2
13195
13