Problem Description

又到了选课的时间了，光头强看着选课表发呆，为了想让下一学期好过点，他想知道学 $n$ 个学分共有多少组合。你来帮帮他吧。（光头强认为一样学分的课没区别）

Input

输入数据的第一行是一个数据 $T$，表示有 $T$ 组数据。

每组数据的第一行是两个整数 $n\ (1 \leq n \leq 40),k\ (1 \leq k \leq 8)$。

接着有 $k$ 行，每行有两个整数 $a\ (1 \leq a \leq 8),b\ (1 \leq b \leq 10)$，表示学分为 $a$ 的课有 $b$ 门。

Output

对于每组输入数据，输出一个整数，表示学 $n$ 个学分的组合数。

Samples

2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8

2
445