Допоможіть BerLine

Зовсім скоро в Берляндії розпочне роботу новий оператор мобільного зв'язку "БерЛайн"!

Старт обслуговування клієнтів планується по центральній вулиці столиці. Вже встановлено $n$ базових станцій. Вони розташовані одна за одною вздовж головної вулиці в порядку від $1$-го до $n$-го зліва направо.

Наразі всі ці базові станції вимкнені. Вони будуть вмикатися по одній, по одній базовій станції на день, за певною перестановкою $p=[p_1,p_2,...,p_n](1\le p_i\le n)$, де $p_i$ — номер базової станції, яка буде включена в $i$-ий день. Таким чином, для включення всіх базових станцій знадобиться $n$ днів.

Кожна базова станція характеризується своєю робочою частотою $f_i$ — цілим числом від $1$ до $24$ включно.

Існує важлива вимога до робочих частот базових станцій. Розглянемо довільний момент часу. Для будь-якого власника телефону, якщо врахувати всі включені базові станції в зоні його доступу, то в цьому наборі базових станцій повинна бути хоча б одна, робоча частота якої є унікальною серед частот цих станцій. Оскільки потужність телефону і його місцезнаходження не відомі заздалегідь, то для будь-якого непустого підрядка включених базових станцій хоча б одна з них повинна мати робочу частоту, унікальну серед станцій цього підсегмента.

Наприклад, розглянемо випадок $n=7$, всі $n$ станцій включені, а їх частоти дорівнюють $f=[1,2,1,3,1,2,1]$. Розглянемо будь-який підрядок базових станцій - в цьому підсегменті є базова станція з унікальною частотою. Однак якщо $f=[1,2,1,2,3,2,1]$, то на відрізку $[1,2,1,2]$ від індексу $1$ до індексу $4$ включно унікальної частоти немає.

Ваше завдання - призначити частоту від $1$ до $24$ кожній з $n$ базових станцій таким чином, щоб потреба в частоті виконувалася в кожний момент часу. Пам'ятайте, що базові станції вмикаються в порядку заданої перестановки $p$.

Вхідні дані

Перша рядок містить ціле число $t(1\le t\le 50)$ — кількість тестів. Далі йдуть $t$ тестів.

Перша рядок кожного тесту містить ціле число $n(1\le n\le 8500)$ — кількість базових станцій "БерЛайн".

Наступний рядок містить $n$ різних цілих чисел $p_1,p_2,...,p_n(1\le p_i\le n)$ — порядок включення базових станцій, тобто в $i$-ий день включається базова станція з індексом $p_i$.

Гарантується, що правильна відповідь існує для всіх вхідних тестів.

Вихідні дані

Виведіть рівно $t$ рядків, де $j$-й рядок містить відповідь для $j$-го тесту. Виведіть потрібні частоти $f_1,f_2,...,f_n(1\le f_i\le 24)$. Якщо можливих відповідей декілька, виведіть будь-яку з них.

Приклади

У першому тесті $n=3$ і $p=[1,3,2]$. Базовим станціям можуть бути призначені частоти $[1,3,2]$.

• День $1$: включена тільки базова станція $1$, її частота $1$.

• День $2$: включені базові станції $1$ і $3$, їх частоти $[1,2]$.

• День $3$: всі базові станції включені, їх частоти $[1,3,2]$ (вздовж вулиці).

Кожен день у кожному непустому підрядку включених базових станцій знаходиться базова станція з унікальною частотою. Можна показати, що в цьому тесті необхідні три різні частоти.