Bob 最近刚学会了寻找生成树的算法，并想给你出一道题。

回顾一下，生成树是图 $G$ 的一个子集，它覆盖了所有顶点且边数最少。因此，生成树没有环且是连通的。给定一个任意的无向简单图（没有重边和自环），生成树移除定义为：从图中取出一棵生成树，并从原图中删除该生成树所选的所有边，从而得到一个新的图。

Bob 觉得“生成树移除”非常有趣，以至于他想反复进行这个操作。特别地，他从一个完全图开始，即每对不同的顶点都由一条唯一的边连接的图。你的目标是巧妙地选择要移除的生成树，以便尽可能多地重复该操作，直到图中不再存在生成树为止。

输入格式

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

每个测试用例占一行：$N$ ($2 \le N \le 1000$)，表示初始图的顶点数。

单个输入中所有测试用例的 $N$ 之和不超过 $1000$。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是从 1 开始的测试用例编号，$y$ 是你最多可以进行移除操作的次数。

接下来输出 $y \times (N - 1)$ 行。从第 $(N - 1) \times (i - 1) + 1$ 行到第 $(N - 1) \times i$ 行，你应该输出你在第 $i$ 次移除时选择的生成树，格式如下：每行包含两个数字 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)。$(u, v)$ 必须是有效的树边，且不能与之前移除过的边重复。如果有多种方案，输出其中任意一种即可。

样例

输入 1

3
2
3
4

输出 1

Case #1: 1
1 2
Case #2: 1
3 1
1 2
Case #3: 2
1 3
3 4
2 4
3 2
1 4
2 1