Raising Modulo Numbers

来源：POJ 1995（CTU Open 1999）

描述

每位玩家选两个数 $A_i$ 和 $B_i$ 写在纸条上，然后一起亮出来。要计算所有 $A_i^{B_i}$ 之和再对给定的 $M$ 取余，最先算对的人获胜。

输入格式

输入包含 $Z$ 组数据，第一行是数据组数 $Z$。

每组数据第一行是整数 $M$（$1 \le M \le 45000$），第二行是整数 $H$ （$1 \le H \le 45000$），随后 $H$ 行每行两个整数 $A_i, B_i$ （$1 \le A_i, B_i \le 45000$）。

输出格式

每组数据输出一行，即 $(A_1^{B_1}+A_2^{B_2}+\dots+A_H^{B_H}) \bmod M$。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
133
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

样例输出

1
2
32
13195
13

数据范围

$1 \le M \le 45000$，$1 \le H \le 45000$，$1 \le A_i, B_i \le 45000$。