描述

人是不一样的。有些人偷偷地阅读杂志，里面全是有趣的女孩子的照片，有些人在自己的地下室里制造一个原子弹，有些人喜欢使用 Windows，还有一些人喜欢高难度的数学游戏。最新的市场研究表明，这一市场细分迄今为止被低估了，而且缺乏此类游戏。这种游戏因此被纳入了 KOKODáKH。游戏规则如下： 每个玩家选择两个数字 Ai 和 Bi，然后把它们写在一张纸条上。其他人看不到数字。在给定的时刻，所有的玩家都向其他玩家展示他们的数字。目标是确定包括自己在内的所有玩家的所有表达式 Ai^Bi 的总和，并确定除以给定数字 M 后的余数。赢家是第一个决定正确结果的人。根据玩家的经验，可以通过选择更高的数字来增加难度。 你应该编写一个程序来计算结果，并能够找出谁赢得了比赛。

输入

输入由 Z 个任务组成。它们的数量由出现在输入第一行的单个正整数 Z 给出。然后是各个任务。每个任务以包含一个整数 M (1 <= M <= 45000) 的行开始。总和将除以这个数。下一行包含玩家数量 H (1 <= H <= 45000)。接下来正好有 H 行。在每一行上，正好有两个数字 Ai 和 Bi，用空格分隔。两个数字不能同时为零。

输出

对于每个任务，只有一行输出。在这一行上，有一个数字，它是表达式 $((A_1 ^ {B_1} + A_2 ^ {B_2} +$... $+ A_H ^ {B_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

此翻译参考了搜索结果中提供的多个中文翻译版本，并对术语和表达进行了统一，以确保准确性和可读性。