Byteasar 是 Byteotia 最受欢迎的火车线路上的列车员。这条线路上有 $m$ 个车站，编号从 $1$ 到 $m$。由于乘客可能在任何车站上车或下车，Byteasar 需要在每两个相邻车站之间检查车票，以确保每位乘客都持有有效的车票。然而，这太耗时了，因为列车员除了查票还有其他职责。

Byteasar 决定系统地解决这个难题。他确定了路线上 $n$ 个最受欢迎的（即最常被乘坐的）路段。他用一对 $(a_i, b_i)$ 表示每个路段，其中 $a_i$ 是乘客上车的车站编号，$b_i$ 是乘客下车的车站编号。Byteasar 希望在确保每位乘坐这 $n$ 个热门路段之一的乘客至少被查票一次的前提下，使查票次数最少。也就是说，对于每个路段 $(a_i, b_i)$，在车站 $a_i$ 和 $b_i$ 之间必须至少有一次查票。出于实际原因，我们假设查票不能在火车停靠车站时进行。

此外，Byteasar 意识到他必须改变查票时间，否则频繁通勤的乘客很快就会发现他的规律，并可能修改他们的路线以避开检查。因此，Byteasar 希望了解所有最小查票方案。如果两个方案在某两个相邻车站之间是否存在查票这一情况上有所不同，则认为这两个方案不同。实际上，对于 Byteasar 而言，只需知道不同最小查票方案总数对 $1\,000\,000\,007$ 取模后的结果即可。

输入格式

标准输入的第一行包含一个整数 $z \ge 1$，表示需要解决的测试用例数量。接下来是这些测试用例的描述，每个测试用例格式如下：

描述的第一行包含两个整数 $m$ 和 $n$ ($1 \le m \le 10^9, 1 \le n$)，用空格分隔，分别表示车站数量和热门路段数量。接下来 $n$ 行描述这些路段：第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i < b_i \le m$)，用空格分隔；这意味着第 $i$ 个热门路段从车站 $a_i$ 开始，在车站 $b_i$ 结束。

每个有序对 $(a_i, b_i)$ 在单个测试用例中最多出现一次。

输出格式

输出 $z$ 行，包含各测试用例的答案。第 $i$ 行应包含两个用空格分隔的整数：满足 Byteasar 要求的最小查票次数，以及不同最小查票方案的总数对 $1\,000\,000\,007$ 取模的结果。

样例

输入 1

2
11 4
1 4
6 8
2 7
9 10
3 2
1 2
2 3

输出 1

3 5
2 1

说明

在第一个测试用例中，需要三次查票来覆盖所有四个热门路段。下图描绘了一种可能的查票方案：在火车离开车站 $\{2, 6, 9\}$ 后进行查票。其余的查票方案为：$\{2, 7, 9\}, \{3, 6, 9\}, \{3, 7, 9\}$ 和 $\{1, 6, 9\}$；总共有五种最小查票方案。

子任务

测试集由以下子集组成。在每个子集中，可能包含多个测试用例。下表中，$z$ 表示给定子集中的测试用例数量，$N$ 表示该子集中所有测试用例的 $n$ 之和。

如果你的程序（对于子集内的每个测试用例）输出了正确的最小查票次数，将获得该子集 20% 的分数。在这种情况下，程序仍应为每个测试用例输出两个数字，其中第二个数字应能放入 32 位有符号整数类型中。