B. Lazy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lavender is too lazy to come up with a good problem, so he will recycle one from two years ago!

Given an array $$$a$$$ of $$$n$$$ integers. Initially, you can choose a number $$$s$$$, and mark the s-th element as used. Then, you need to perform the following operation $$$n-1$$$ times:

  • On the $$$x$$$-th operation, choose two numbers $$$u$$$ and $$$v$$$ such that the $$$u$$$-th element is used, the $$$v$$$-th element is not used, and $$$|a_{u} - a_{v}|$$$ is divisible by $$$x$$$.
  • Mark the $$$v$$$-th element as used.

You have to determine if it is possible to perform all $$$n-1$$$ operations. If so, output any valid operation sequence.

Input

Each test consists of multiple test cases. The first line contains an integer t ($$$1\leq t\leq 100$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains the number n ($$$2\leq n\leq 2000$$$) — the number of elements in the array.

The second line of each test case contains n numbers $$$a_{1},a_{2},\ldots 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

For each test case, if there is no solution, then output "NO" (without quotes).

Otherwise, output "YES" (without quotes), and then output a number $$$s$$$ on the first line, denoting the first used element. In the next $$$n-1$$$ lines, output the numbers $$$u_{i}$$$ and $$$v_{i}$$$ ($$$u\neq v$$$), denoting the two chosen number for operation $$$i$$$.

Example
Input
8
2
1 4
4
99 7 1 13
5
10 2 31 44 73
5
87 6 81 44 32
5
62 35 33 79 16
5
6 51 31 69 42
5
52 63 25 21 5
12
33 40 3 11 31 43 37 8 50 5 12 22
Output
YES
1
1 2
YES
1
1 4
1 2
2 3
YES
1
1 5
1 4
1 3
1 2
YES
1
1 4
1 3
1 2
4 5
YES
1
1 3
1 5
1 2
2 4
YES
1
1 4
1 5
1 2
2 3
YES
1
1 2
2 5
1 3
3 4
YES
1
1 9
9 12
1 11
1 10
1 6
6 7
1 2
2 8
2 5
1 3
1 4
Note

In the first testcase, you can also choose $$$s=2$$$, $$$u_{1}=2$$$, and $$$v_{1}=1$$$.

In the second testcase:

  • $$$|a_{1}-a_{4}| = |99-13| = 86$$$ is divisible by $$$1$$$
  • $$$|a_{1}-a_{2}| = |99-7| = 92$$$ is divisible by $$$2$$$
  • $$$|a_{2}-a_{3}| = |7-1| = 6$$$ is divisible by $$$3$$$.
It can be observed that all chosen $$$u$$$ are previously used, and all chosen $$$v$$$ were previously not used.