Это интерактивная задача!

Существует скрытый массив $a_1, a_2, \dots, a_N$ из $N$ различных положительных целых чисел (где $N$ нечётно); некорректная копия этого массива хранится в другом скрытом массиве $b$. Каждый элемент массива $b$ определяется следующим образом:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ или $b_i = a_{i+1}$ для каждого $i$, где $1 < i < N$ (один из соседних элементов)

Вам нужно определить, существуют ли два индекса $i$ и $j$ ($i \neq j$, $1 \le i, j \le N$) такие, что $b_i = b_j$. Если такие индексы существуют, верните их; в противном случае укажите, что таких индексов не существует.

Вы можете запрашивать элементы массивов $a$ и $b$ с помощью следующих операций:

• 1 i: возвращает значение $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: возвращает значение $b_i$ ($1 \le b_i \le 10^9$)

Вы можете сделать не более 20 запросов.

Протокол взаимодействия

Сначала вы должны считать строку, содержащую одно целое число $T$ ($1 \le T \le 100$), обозначающее количество тестовых наборов.

Затем следует взаимодействие для $T$ тестовых наборов.

Для каждого тестового набора вы должны сначала считать строку, содержащую одно целое число $N$ ($3 \le N \le 2\,001$, $N$ нечётно).

Затем начинается взаимодействие. Вы можете вывести одну строку, содержащую:

• 1 x (Спросить о $a_x$): Затем считайте одну строку, состоящую из одного целого числа — $a_x$.
• 2 x (Спросить о $b_x$): Затем считайте одну строку, состоящую из одного целого числа — $b_x$.
• 3 i j (Ответ: два индекса $i, j$, где $b_i = b_j$, или -1 -1, если таких двух индексов нет): Затем перейдите к следующему тесту, если он есть; в противном случае завершите работу.

После вывода каждой строки не забывайте сбрасывать буфер вывода (flush). Например:

• fflush(stdout) в C/C++;
• System.out.flush() в Java;
• sys.stdout.flush() в Python;
• flush(output) в Pascal;
• Обратитесь к документации для других языков.

Пример

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

1
7
2
2

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

2 3
2 1
3 1 3