去年，Rounddog 参加了一场题目集非常困难的比赛，并且没能解决关于线图的问题。因此，最近他决定更深入地研究它们。

在图论这一数学学科中，简单无向图 $G$ 的线图 $L(G)$ 是另一个简单无向图，它表示了 $G$ 中每两条边之间的邻接关系。准确地说，对于一个没有自环或重边的无向图 $G$，其线图 $L(G)$ 是一个满足以下条件的图：

• $L(G)$ 的每个顶点代表 $G$ 的一条边；且
• $L(G)$ 的两个顶点相邻，当且仅当它们对应的边在 $G$ 中共享一个公共端点。

给定一个简单无向图 $G$，Rounddog 的研究旨在寻找其线图 $L(G)$ 中的最大团，他决定将他的一些发现变成一个挑战给你。

在本题中，给定一个简单无向图 $G$ 和一个较小的正整数 $k$。在找到 $L^k(G)$ 中的所有最大团后（其中 $L^0(G) = G$，且对于每个正整数 $s$，$L^s(G) = L(L^{s-1}(G))$），你需要告诉 Rounddog $L^k(G)$ 中最大团的顶点数，以及不同最大团的数量（对 $1\,000\,000\,007$ 取模）。

在此，无向图的顶点子集被称为团，当且仅当该子集中的每对顶点之间都有一条边，而最大团是指顶点数最多的团。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n$ ($1 \le n \le 100\,000$)、$m$ ($0 \le m \le 200\,000$) 和 $k$ ($1 \le k \le 4$)：分别表示给定简单无向图 $G$ 的顶点数、边数以及线图操作的迭代次数。

接下来 $m$ 行，描述图的所有边。每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示顶点 $u$ 和 $v$ 之间的一条边。

保证所有测试用例中 $n$ 的总和不超过 $2\,000\,000$，$m$ 的总和不超过 $3\,000\,000$，且每个测试用例中的图都不包含自环或重边。

输出格式

对于每个测试用例，输出一行，包含两个整数：第一个是最大团的顶点数，第二个是不同最大团的数量（对 $1\,000\,000\,007$ 取模）。

样例

输入格式 1

3
5 0 4
5 4 1
1 2
1 3
1 4
1 5
5 4 4
1 2
1 3
1 4
1 5

输出格式 1

0 1
4 1
6 12