题目描述

你是大鱼，一天你在海里划水。

海可以看成一个坐标平面，海上有 $n$ 座小岛，第 $i$ 座小岛的坐标为 $\left( x_i, y_i \right)$，上面居住着 $i$ 个人。

你喜欢沿着平行于 $x$ 轴或 $y$ 轴的方向进行划水，你觉得一条划水的路线是快乐的，如果它满足如下条件：

1. 该路线平行于 $x$ 轴，从纵坐标负无穷远处划到正无穷远处；或该路线平行于 $y$ 轴，从横坐标负无穷远处到正无穷远处。
2. 沿着你划水的方向，至少经过一座小岛。
3. 你会求出沿途经过的所有小岛的人数的最大公约数，这个数最终为 $1$。

(ps: 特别地，定义一个数的最大公约数就是它本身)

你希望有尽可能多的快乐的划水路线，于是你找到了水神，希望她帮你控制这片海域来完成你的目标。

不幸的是，水神不能改变这些小岛的坐标，她只能调整每座小岛的人数，且需要保持 $n$ 座小岛的人数恰为 $1 \sim n$ 的一个排列。

不过水神的计算能力不怎么好，因此她需要你给出一组方案，然后她会按照你的方案来重新分配这 $n$ 座小岛的人数。

因此你的任务是：找出一组调整小岛人数的方案，使得在满足水神的条件下，快乐的划水路线数尽可能多。

输入格式

本题包含多组数据。

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含一个正整数 $n$，表示小岛的个数。

接下来 $n$ 行，每行两个正整数 $x_i, y_i$，表示一座小岛的坐标。保证所有小岛的坐标两两不同。

输出格式

对于每组数据，输出两行：

第一行输出一个整数，表快乐的划水路线的数量的最大可能值。

第二行输出 $n$ 个整数，表示每座小岛的人数，按照输入的顺序输出。你需要保证你输出的 $n$ 个数恰为 $1 \sim n$ 的排列。

如果有多组解，输出任意一组均可。

注意：如果你对于所有的数据，第一行的输出均正确，可以获得该子任务 $\color{red}{25 \%}$ 的分数。但是如果你只要这个部分分，你也要在第二行输出一个排列 (但不需要满足你的答案)。

2
4
1 1
1 2
2 1
2 2
5
1 1
2 2
4 4
8 8
16 16

4
1 2 4 3
2
1 2 3 4 5

样例 2

见附加文件中的 ex_coprime2.in 与 ex_coprime2.out。

数据范围与提示

对于所有的测试点，均满足 $1 \leq T, n \leq 2 \times 10^5; \sum n \leq 2 \times 10^5; 1 \leq x_i, y_i \leq 10^9$，对于 $i \neq j$，保证 $x_i \neq x_j \vee y_i \neq y_j$。

具体的子任务的数据规模见下表：

子任务	分值	$n$	$T$	$x_i,y_i$	其他性质
$1$	$4$	$\le 9$	$\le 6$	$\le n$	无
$2$	$4$	$\le 2\times 10^5$	$\le 2\times 10^5$	$\le 10^9$	$x_i = y_i$
$3$	$4$				$y_i = 1$
$4$	$4$				$y_i\le 2$
$5$	$8$	$\le 9$		$\le n$	无
$6$	$8$	$\le 50$	$\le 50$	$\le 10^9$	$\sum n\le 2500$
$7$	$8$	$\le 2500$	$\le 2500$
$8$	$8$	$\le 2\times 10^5$	$=1$		保证所有小岛构成一个 $4-$连通块
$9$	$4$		$\le 2\times 10^5$
$10$	$8$		$=1$		保证每条平行于坐标轴的直线经过的小岛个数不等于 $2$
$11$	$4$		$\le 2\times 10^5$
$12$	$8$		$=1$		保证每条平行于坐标轴的直线经过的小岛个数等于 $0$ 或 $2$
$13$	$4$		$\le 2\times 10^5$
$14$	$8$		$=1$	$\le 10000$	保证所有小岛的坐标在可行域内均匀随机
$15$	$4$		$\le 2\times 10^5$
$16$	$8$		$=1$	$\le 10^9$	无
$17$	$4$		$\le 2\times 10^5$

注：两个整点 $A, B$ 是 $4-$连通的，当且仅当存在一个整点序列 $P_0 = A, P_1, P_2, \cdots, P_{m-1}, P_m = B$，使得 $\left| P_i P_{i+1} \right| = 1$ ($0 \leq i < m$)。

注意：如果你对于所有的数据，第一行的输出均正确，可以获得该子任务 $\color{red}{25 \%}$ 的分数。但是如果你只要这个部分分，你也要在第二行输出一个排列 (但不需要满足你的答案)。（很重要所以说两遍）

此外，为了选手的身心健康，我们在下发文件中准备了一份 checker.cpp，请大家自行编译使用，使用方法及头文件参见 testlib 标准。