Помогите 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]$ (вдоль улицы).

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