Description

给定H对非负整数数对Ai,Bi) 和一个正整数M。

请你计算并输出(A1B1+A2B2+…+AHBH)modM。

Input Format

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含整数M。

第二行包含整数H。

接下来H 行，每行包含两个整数Ai,Bi。

Output Format

每组数据输出一行结果。

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

2
13195
13

Hint

1≤T≤100,
1≤M≤45000,
1≤H≤45000,
0≤Ai,Bi≤107,
Ai 和i 不同时为 0。

Source

快速幂