E1-妙妙趣排序

题面

本题中：

一个即将排好序的序列定义为：将这个序列去除至多一个值后，新序列是严格递增的。

一个过滤器 $[u,v]$ 定义为：一个序列 $a$ 经过过滤器 $[u,v]$ 后，$a_u=min(a_u,a_v)$,$a_v=max(a_u,a_v)$，其他值不变。

妙妙趣排序器由 $k$ 个过滤器组成，一个序列的妙妙趣排序需要依次经过排序器的 $k$ 个过滤器。

那么请问，1~$n$ 的全排列中，有几个序列经过给定的妙妙趣排序后可以变成即将排好序的序列。

输入

第一行一个正整数 $t$ 表示数据组数 ($0<t<100$)。

接下来 $t$ 组数据，

每组数据的第一行，两个整数 $n，k$ ($2\le n\le50,0\le k\le10$)；

每组数据接下来的 $k$ 行，每行两个整数 $u,v$，表示一个过滤器($1\le u<v \le n$)。

输出

每组数据输出一行，一个整数。

输入样例

4
4 0
4 1
1 2
4 3
1 2
2 3
1 2
4 6
1 2
2 3
1 2
3 4
2 3
1 2

输出样例

10
14
24
24