D. Смешная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вани есть граф из $$$n$$$ вершин (пронумерованных от $$$1$$$ до $$$n$$$) и массив $$$a$$$ из $$$n$$$ целых чисел, изначально в графе нет рёбер. Ване стало скучно, и чтобы ему стало весело, он решил выполнить $$$n - 1$$$ операцию.

Операция под номером $$$x$$$ (операции нумеруются по порядку начиная с $$$1$$$) заключается в следующем:

  • Выбрать $$$2$$$ различных числа $$$1 \leq u,v \leq n$$$, таких что $$$|a_u - a_v|$$$ делится на $$$x$$$.
  • Добавить в граф неориентированное ребро между вершинами $$$u$$$ и $$$v$$$.

Помогите Ване с помощью $$$n - 1$$$ операции получить связный$$$^{\text{∗}}$$$ граф, или скажите, что это невозможно.

$$$^{\text{∗}}$$$Граф называется связным, если в нём можно от любой вершины дойти до любой другой, двигаясь по рёбрам.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — количество вершин в графе.

Во второй строке каждого набора входных данных дано $$$n$$$ чисел $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных, если решения не существует, то выведите «No» (без кавычек).

Иначе выведите «Yes» (без кавычек), после этого выведите $$$n - 1$$$ строку, в $$$i$$$-й из них выведите числа $$$u$$$ и $$$v$$$, которые надо выбрать на операции $$$i$$$.

Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).

Пример
Входные данные
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
Выходные данные
YES
2 1
YES
4 1
2 1
3 2
YES
5 1
4 1
3 1
2 1
YES
4 1
3 1
2 1
5 4
YES
3 1
5 1
2 1
4 2
YES
4 1
5 1
2 1
3 2
YES
2 1
5 2
3 1
4 3
YES
9 1
12 9
11 1
10 1
6 1
7 6
2 1
8 2
5 2
3 1
4 1
Примечание

Рассмотрим второй набор входных данных.

  • Первая операция $$$(x = 1)$$$: можно соединить вершины $$$4$$$ и $$$1$$$, так как $$$|a_4 - a_1| = |13 - 99| = |-86| = 86$$$, а $$$86$$$ кратно $$$1$$$.
  • Вторая операция $$$(x = 2)$$$: можно соединить вершины $$$2$$$ и $$$1$$$, так как $$$|a_2 - a_1| = |7 - 99| = |-92| = 92$$$, а $$$92$$$ кратно $$$2$$$.
  • Третья операция $$$(x = 3)$$$: можно соединить вершины $$$3$$$ и $$$2$$$, так как $$$|a_3 - a_2| = |1 - 7| = |-6| = 6$$$, а $$$6$$$ кратно $$$3$$$.
Из картинки видно, что получился связный граф.