Чапаті Султана
Султан Іскетамболи любить, щоб його чапаті подавалися у стопці з унікально розміреними чапаті та підігрівалися особливим чином. Кухар султана повинен підігріти стопку з унікально розміреними чапаті, де кожне чапаті внизу стопки має більший діаметр, ніж те, що знаходиться вище. Ваше завдання — написати програму, яка вказує, як можна відсортувати стопку так, щоб найбільше чапаті було внизу, а найменше — зверху. Розмір чапаті визначається його діаметром. Усі чапаті в стопці мають різні діаметри.
Сортування стопки здійснюється за допомогою послідовності "переворотів" чапаті. Переворот полягає у вставленні лопатки між двома чапаті в стопці та перевертанні (реверсуванні) чапаті на лопатці (реверсуванні підстопки). Переворот задається шляхом вказання позиції чапаті на дні підстопки, яку потрібно перевернути (відносно всієї стопки). Чапаті на дні всієї стопки має позицію 1, а чапаті на вершині стопки з n чапаті має позицію n. Стопка задається шляхом вказання діаметра кожного чапаті в стопці в порядку, в якому чапаті з'являються.
Наприклад, розглянемо три стопки чапаті нижче (в яких чапаті 8 є верхнім чапаті лівої стопки):
8 2 4
6 4 2
1 1 1
4 6 6
2 8 8
Ліву стопку можна перетворити на середню стопку за допомогою перевороту(1). Середню стопку можна перетворити на праву стопку за допомогою команди переворот(4). Останній переворот переворот(3) призведе до відсортованої стопки.
Вхідні дані
Перша строка вхідних даних містить T, кількість тестових випадків (1 ≤ T ≤ 1000). Кожен тестовий випадок складається з двох рядків. Перший рядок тестового випадку містить N (1 ≤ N ≤ 30), кількість чапаті в стопці. Наступний рядок містить N цілих чисел, розділених одним пробілом. Кожне ціле число вказує діаметр чапаті від 1 до 100 з верхньої позиції до нижньої.
Вихідні дані
Для кожного тестового випадку вивід містить рядок у форматі Case #x:, за яким слідує послідовність цілих чисел, де x — номер випадку (починаючи з 1). Для кожної стопки послідовність переворотів повинна завершуватися 0 (що вказує на те, що більше переворотів не потрібно). Як тільки стопка відсортована, більше переворотів не повинно бути.