Чапати Султана
Султан Искетамбола предпочитает, чтобы его чапати подавались в стопке, где каждый чапати имеет уникальный размер, и разогревались особым образом. Повар султана должен разогреть стопку чапати, где каждый чапати внизу стопки больше по диаметру, чем тот, что выше. Вам необходимо написать программу, которая укажет, как отсортировать стопку так, чтобы самый большой чапати оказался внизу, а самый маленький — наверху. Размер чапати определяется его диаметром, и все чапати в стопке имеют разные диаметры.
Сортировка стопки осуществляется с помощью последовательности "переворотов" чапати. Переворот заключается в том, чтобы вставить лопатку между двумя чапати в стопке и перевернуть (реверсировать) чапати на лопатке (реверсировать подстопку). Переворот задается указанием позиции чапати на дне подстопки, которую нужно перевернуть (относительно всей стопки). Чапати на дне всей стопки имеет позицию 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 целых чисел, разделенных одним пробелом. Каждое целое число указывает диаметр чапати от верхней позиции до нижней.
Выходные данные
Для каждого теста вывод содержит строку в формате Case #x:, за которой следует последовательность целых чисел, где x — номер теста (начиная с 1). Для каждой стопки последовательность переворотов должна заканчиваться 0 (что указывает на то, что больше переворотов не требуется). Как только стопка отсортирована, больше переворотов не должно быть.