Little Cyan Fish-те $1$-ден $n$-ге дейінгі бүтін сандардан тұратын $p_1, p_2, \ldots, p_n$ алмастыруы бар және есептің атауы меңзеп тұрғандай, ол оны өсу ретімен сұрыптағысы келеді. Бұл жолы ол орындай алатын амал төмендегідей.

• Бір амалда Little Cyan Fish $1 \le i < j \le n$ шартын қанағаттандыратын екі бүтін $i$ және $j$ сандарын таңдап, $p_i$ мен $p_j$ элементтерінің орындарын ауыстыра алады.

Бірақ, қойыңызшы, алмастыруды қарапайым орын ауыстырулар арқылы қалай сұрыптау керектігін бәрі біледі, сондықтан есеп сізден мұны талап етпейтіні анық. Оның орнына, Little Cyan Fish амалдың арақашықтығын $j - i$ деп анықтайды. Алмастыруды сұрыптайтын амалдар тізбегі үшін, әрбір $1 \le d < n$ үшін $a_d$ арқылы арақашықтығы $d$-ға тең амалдар санын белгілейік.

Алмастыруды сұрыптайтын барлық ақырлы амалдар тізбектерінің ішінен Little Cyan Fish сізден лексикографиялық тұрғыдан ең кіші $(a_1, a_2, \ldots, a_{n-1})$ тізбегін табуды және оған қол жеткізетін ең көп дегенде $5n$ амалдан тұратын тізбек құрастыруды қалайды.

Кіріс деректер

Бірнеше тест жағдайлары берілген. Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^6$) берілген.

Әрбір тест жағдайы үшін бірінші жолда алмастырудың ұзындығын білдіретін бір бүтін сан $n$ ($2 \le n \le 10^6$) берілген. Екінші жолда алмастыруды білдіретін $n$ бүтін сан $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) берілген. $p$ ұзындығы $n$ болатын алмастыру екеніне кепілдік беріледі.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $10^6$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін жауапты келесі форматта шығарыңыз.

Әрбір тест жағдайының бірінші жолында лексикографиялық тұрғыдан ең кіші тізбек болатын $n - 1$ бүтін сан $a_1, a_2, \ldots, a_{n-1}$ болуы тиіс.

Екінші жолда сіздің тізбегіңіздегі амалдар санын білдіретін бір бүтін сан $k$ ($0 \le k \le 5n$) болуы тиіс.

Келесі $k$ жолдың әрқайсысында сәйкес амалда таңдалған индекстерді білдіретін екі бүтін сан $i$ және $j$ ($1 \le i < j \le n$) болуы тиіс. Берілген ретпен орындалған амалдар кіріс алмастыруын сұрыптауы тиіс және әрбір $1 \le d < n$ үшін амалдардың дәл $a_d$ данасының арақашықтығы $d$ болуы тиіс.

Ең көп дегенде $5n$ амалдан тұратын оңтайлы тізбек әрқашан табылатынын көрсетуге болады. Егер бірнеше жарамды амалдар тізбегі болса, олардың кез келгенін шығаруға болады.

Мысалдар

Кіріс деректер 1

3
3
3 2 1
4
2 1 3 4
4
1 3 2 4

Шығыс деректер 1

0 1
1
1 3
0 1 2
3
1 4
2 4
1 4
0 3 2
5
1 3
1 4
2 4
1 4
1 3

Ескертпе

Бірінші мысалдағы тест жағдайында Little Cyan Fish $1$ және $3$ орындарын ауыстырады. Бұл арақашықтығы $2$ болатын бір амалдың көмегімен алмастыруды сұрыптайды.

Екінші мысалдағы тест жағдайында оңтайлы тізбектердің бірі — $(1, 4)$, $(2, 4)$, $(1, 4)$. Арақашықтықтары сәйкесінше $3$, $2$ және $3$, сондықтан нәтижелік тізбек $(0, 1, 2)$ болады.

Үшінші мысалдағы тест жағдайында оңтайлы тізбектердің бірі — $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Оның арақашықтықтар бойынша амалдар саны — $(0, 3, 2)$.