你是大魚，一天你在海裡划水。

海可以看成一個座標平面，海上有 $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 \%}$ 的分數。但是如果你只要這個部分分，你也要在第二行輸出一個排列 (但不需要滿足你的答案)。

範例

範例 1 輸入

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

範例 1 輸出

4
1 2 4 3
2
1 2 3 4 5

說明 1

對於第一組數據：

快樂的划水路線有四條：$x = 1$ (沿途經過的小島人數分別為 $1, 2$)、$x = 2$ (人數分別為 $4, 3$)、$y = 1$ (人數分別為 $1, 4$)、$y = 2$ (人數分別為 $2, 3$)。

對於第二組數據：

快樂的划水路線有兩條：$x = 1$ (人數分別為 $1$)、$y = 1$ (人數分別為 $1$)。

範例 2

見下發文件

子任務

對於所有的測試點，均滿足 $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$。

具體的子任務的數據規模見下表：

註：兩個整點 $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 標準。