由于 Bytecity 的犯罪率居高不下，新任市长决定雇佣来自 $c$ 个不同安保公司的安保人员。作为第一步，他将在 Bytecity 中每两条道路的交点处安排一名来自任意一家公司的安保人员。

Bytecity 拥有一个非常特殊且复杂的交通系统。城市中有 $n$ 条笔直且漫长的道路，每一条都可以看作二维平面上的一条无限长直线，且不存在 3 条或更多道路交于同一点的情况。

为了防止安保人员在工作中偷懒，市长决定在任意两个相邻的交点处安排来自不同安保公司的安保人员。我们称两个交点是相邻的，如果它们位于同一条道路上，且在该道路上这两个交点之间不存在其他交点。此外，市长认为安保公司的数量越少越易于管理。你能帮助市长以尽可能少的安保公司来分配所有交点吗？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的总数。每个测试用例的第一行是一个整数 $n$，表示 Bytecity 中的道路数量。接下来的 $n$ 行描述了 Bytecity 中的道路，第 $i$ 行包含 4 个整数 $x_{1i}, y_{1i}, x_{2i}, y_{2i}$，表示第 $i$ 条道路是经过平面上 $(x_{1i}, y_{1i})$ 和 $(x_{2i}, y_{2i})$ 的直线。

• $1 \le T \le 1000$。
• $2 \le n \le 1000$。
• $-10^3 \le x_{1i}, y_{1i}, x_{2i}, y_{2i} \le 10^3$。
• $(x_{1i}, y_{1i}) \neq (x_{2i}, y_{2i})$。
• 至多有 10 个测试用例满足 $n > 100$。
• 不存在两条相同的道路，且每个测试用例中至少存在 1 个交点。

输出格式

对于每个测试用例，请在第一行输出一个整数 $c$，表示你安排中所使用的最少不同公司数量。接下来的 $n-1$ 行中，第 $i$ 行应包含整数 $a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$。数字 $a_{i,j}$ 表示管理道路 $i$ 和道路 $j$ 交点的安保公司编号；如果交点不存在，则 $a_{i,j}$ 应为 $-1$。

注意，所有公司应编号为从 $1$ 到 $c$ 的整数，任何满足市长要求的安排均可被接受。

样例

输入 1

2
3
0 0 1 0
0 0 0 1
1 0 0 1
3
0 0 1 0
0 1 0 2
1 0 1 1

输出 1

3
1 2
3
2
2 1
-1