Грейдер читает тест в следующем формате:

В первой строке указано число $t$ ($1 \le t \le 30\,000$)~--- количество наборов входных данных.

Первая строка каждого набора входных данных содержит \textbf{нечетное} число $n$ ($1 \le n \le 30\,000$)~--- длину перестановки.

Вторая строка содержит $n$ различных чисел $p_1, \ldots, p_n$ ($1 \le p_i \le n$)~--- загаданную перестановку.