You are Big Fish, and you are swimming in the sea.
The sea can be viewed as a coordinate plane with $n$ islands. The $i$-th island is located at $(x_i, y_i)$ and is inhabited by $i$ people.
You like to swim along paths parallel to the $x$-axis or $y$-axis. A swimming path is considered "happy" if it satisfies the following conditions:
- The path is parallel to the $x$-axis, extending from $x = -\infty$ to $x = +\infty$; or the path is parallel to the $y$-axis, extending from $y = -\infty$ to $y = +\infty$.
- The path passes through at least one island.
- The greatest common divisor of the number of people on all islands along the path is $1$.
(ps: Specifically, the greatest common divisor of a single number is defined as the number itself.)
You want to have as many happy swimming paths as possible, so you ask the Water God to help you control this sea area to achieve your goal.
Unfortunately, the Water God cannot change the coordinates of the islands; she can only adjust the number of people on each island, provided that the number of people on the $n$ islands remains a permutation of $1 \sim n$.
However, the Water God is not very good at calculations, so she needs you to provide a plan, and she will reassign the number of people on the $n$ islands according to your plan.
Therefore, your task is: find a plan to adjust the number of people on the islands such that the number of happy swimming paths is maximized, subject to the Water God's conditions.
Input
The input contains multiple test cases.
The first line contains a positive integer $T$, representing the number of test cases.
For each test case, the first line contains a positive integer $n$, representing the number of islands.
The next $n$ lines each contain two positive integers $x_i, y_i$, representing the coordinates of an island. It is guaranteed that all island coordinates are distinct.
Output
For each test case, output two lines:
The first line outputs an integer, representing the maximum possible number of happy swimming paths.
The second line outputs $n$ integers, representing the number of people on each island, in the order of the input. You must ensure that the $n$ numbers you output are a permutation of $1 \sim n$.
If there are multiple solutions, any one of them is acceptable.
Note: If you output the correct value for the first line for all test cases, you can receive $25\%$ of the score for that subtask. However, even if you only want this partial score, you must still output a permutation on the second line (it does not need to satisfy your answer).
Examples
Input 1
2 4 1 1 1 2 2 1 2 2 5 1 1 2 2 4 4 8 8 16 16
Output 1
4 1 2 4 3 2 1 2 3 4 5
Note 1
For the first test case:
There are four happy swimming paths: $x = 1$ (the number of people on the islands passed are $1, 2$), $x = 2$ (the number of people are $4, 3$), $y = 1$ (the number of people are $1, 4$), $y = 2$ (the number of people are $2, 3$).
For the second test case:
There are two happy swimming paths: $x = 1$ (the number of people is $1$), $y = 1$ (the number of people is $1$).
Examples 2
See the provided files.
Subtasks
For all test cases, $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$. For $i \neq j$, it is guaranteed that $x_i \neq x_j \vee y_i \neq y_j$.
The data scale for specific subtasks is shown in the table below:
| Subtask | Score | $n$ | $T$ | $x_i, y_i$ | Other Properties |
|---|---|---|---|---|---|
| $1$ | $4$ | $\le 9$ | $\le 6$ | $\le n$ | None |
| $2$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $x_i = y_i$ |
| $3$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i = 1$ |
| $4$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i \le 2$ |
| $5$ | $8$ | $\le 9$ | $\le 2\times 10^5$ | $\le n$ | None |
| $6$ | $8$ | $\le 50$ | $\le 50$ | $\le 10^9$ | $\sum n \le 2500$ |
| $7$ | $8$ | $\le 2500$ | $\le 2500$ | $\le 10^9$ | $\sum n \le 2500$ |
| $8$ | $8$ | $\le 2\times 10^5$ | $= 1$ | $\le 10^9$ | All islands form a $4$-connected component |
| $9$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | All islands form a $4$-connected component |
| $10$ | $8$ | $\le 2\times 10^5$ | $= 1$ | $\le 10^9$ | Number of islands on each axis-parallel line is not $2$ |
| $11$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Number of islands on each axis-parallel line is not $2$ |
| $12$ | $8$ | $\le 2\times 10^5$ | $= 1$ | $\le 10^9$ | Number of islands on each axis-parallel line is $0$ or $2$ |
| $13$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Number of islands on each axis-parallel line is $0$ or $2$ |
| $14$ | $8$ | $\le 2\times 10^5$ | $= 1$ | $\le 10000$ | Coordinates are uniformly random in the feasible region |
| $15$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10000$ | Coordinates are uniformly random in the feasible region |
| $16$ | $8$ | $\le 2\times 10^5$ | $= 1$ | $\le 10^9$ | None |
| $17$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | None |
Note: Two integer points $A, B$ are $4$-connected if and only if there exists a sequence of integer points $P_0 = A, P_1, P_2, \cdots, P_{m-1}, P_m = B$ such that $|P_i P_{i+1}| = 1$ ($0 \leq i < m$).
Note: If you output the correct value for the first line for all test cases, you can receive $25\%$ of the score for that subtask. However, even if you only want this partial score, you must still output a permutation on the second line (it does not need to satisfy your answer). (This is important, so it is said twice.)
In addition, for the sake of the contestants' mental health, we have prepared a checker.cpp in the provided files. Please compile and use it yourself. For usage and header files, refer to the testlib standard.