Link 正在玩一个名为“出租广告位”（Advertising Space for Rent）的游戏。

在这个游戏中，一个关卡由若干个世界组成。每个世界包含 $m$ 个节点和一些有向道路。玩家从第一个世界的节点 1 开始。在每个世界中，玩家可以选择停留在当前节点，或者通过该世界中存在的恰好一条道路。之后，玩家会被传送到下一个世界，且保持所在的节点编号不变。如果没有下一个世界，游戏结束。如果玩家最终停留在节点 $m$，则视为获胜。

Link 正在编辑一个新的关卡，他已经制作了 $n$ 个世界（编号从 1 到 $n$），并希望从中选择一个连续的子段来组成一个新关卡。唯一的限制是获胜的方法不能超过 $k$ 种。（当且仅当在某个世界中的操作不同时，两种获胜方法被视为不同。）

Link 不想丢弃太多的世界。请问 Link 在新关卡中最多可以使用多少个世界？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 30$)。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n \le 5 \times 10^3, 2 \le m \le 20, 1 \le k \le 10^9$)。

接下来的输入描述了从 1 到 $n$ 的世界。对于每个世界： 第一行包含一个整数 $l$ ($0 \le l \le m \times (m - 1)$)，表示该世界中道路的数量。 接下来的 $l$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le m, u \neq v$)，表示该世界中存在一条从节点 $u$ 到节点 $v$ 的道路。

对于每个世界，保证没有重复的边。

对于每个测试用例，保证所有 $l$ 的总和不超过 $10^6$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，且所有测试用例中 $l$ 的总和不超过 $3 \times 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示 Link 在新关卡中最多可以使用世界的数量。

样例

样例输入 1

2
3 3 1
1
2 1
1
2 3
1
1 2
3 3 1
1
1 2
1
1 2
1
2 3

样例输出 1

3
2