1994D · Funny Game

Problem: Vanya has a graph with $n$ vertices (numbered from $1$ to $n$) and an array $a$ of $n$ integers; initially, there are no edges in the graph. Vanya got bored, and to have fun, he decided to perform $n - 1$ operations.

Operation number $x$ (operations are numbered in order starting from $1$) is as follows:

• Choose $2$ different numbers $1 \leq u,v \leq n$, such that $|a_u - a_v|$ is divisible by $x$.
• Add an undirected edge between vertices $u$ and $v$ to the graph.

Help Vanya get a connected$^{\text{*}}$ graph using the $n - 1$ operations, or determine that it is impossible.

Input Format: Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^{3}$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains the number $n$ ($1 \leq n \leq 2000$) — the number of vertices in the graph.

The second line of each test case contains $n$ numbers $a_1, a_2, \cdots a_n$ ($1 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output Format: For each test case, if there is no solution, then output "No" (without quotes).

Otherwise, output "Yes" (without quotes), and then output $n - 1$ lines, where in the $i$-th line, output the numbers $u$ and $v$ that need to be chosen for operation $i$.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Note: Let's consider the second test case.

• First operation $(x = 1)$: we can connect vertices $4$ and $1$, since $|a_4 - a_1| = |13 - 99| = |-86| = 86$, and $86$ is divisible by $1$.

• Second operation $(x = 2)$: we can connect vertices $2$ and $1$, since $|a_2 - a_1| = |7 - 99| = |-92| = 92$, and $92$ is divisible by $2$.

• Third operation $(x = 3)$: we can connect vertices $3$ and $2$, since $|a_3 - a_2| = |1 - 7| = |-6| = 6$, and $6$ is divisible by $3$.