Совсем скоро в Берляндии начнет работу новый оператор сотовой связи "БерЛайн"! Старт обслуживания клиентов планируется по центральной улице столицы. Уже установлено $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$. \InputFile Первая строка содержит целое число $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$. Гарантируется, что правильный ответ существует для всех входных тестов. \OutputFile Выведите ровно $t$ строк, где $j$-я строка содержит ответ для $j$-го теста. Выведите требуемые частоты $f_1, f_2, ..., f_n~(1 \le f_i \le 24)$. Если возможных ответов несколько, выведите любой из них. \Examples В первом тесте $n = 3$ и $p = [1, 3, 2]$. Базовым станциям могут быть назначены частоты $[1, 3, 2]$. \begin{itemize} \item День $1$: включена только базовая станция $1$, ее частота $1$. \item День $2$: включены базовые станции $1$ и $3$, их частоты $[1, 2]$. \item День $3$: все базовые станции включены, их частоты $[1, 3, 2]$ (вдоль улицы). \end{itemize} Каждый день в каждом непустом подотрезке включенных базовых станций находится базовая станция с уникальной частотой. Можно показать, что в этом тесте необходимы три различные частоты.