Кран#6774
Є ящиків, які потрібно завантажити на корабель. Ящики пронумеровані від до , і ці номери визначають порядок завантаження. На жаль, ящики розташовані в довільному порядку. Через обмежений простір у доковій зоні, ви повинні відсортувати ящики, обмінюючи деякі з них.
Вам надано кран, який працює так: ви вибираєте підрядний інтервал ящиків парної довжини. Кран обмінює першу половину інтервалу з другою половиною, зберігаючи порядок всередині кожної половини. Визначте послідовність рухів крана, яка правильно впорядковує ящики.
У програмному забезпеченні крана є помилка: лічильник рухів працює в -ковій системі числення (не -ковій, як можна було б очікувати) і може відображати не більше ніж цифр. Тому кран перестає працювати (і потребує обслуговування) після 9^6 = 531441 рухів. Ваше рішення має вміститися в цей ліміт.
Перший рядок вхідних даних містить кількість тестових випадків . Опис тестових випадків наступний:
Кожен тестовий випадок починається з цілого числа , 1 \leq n \leq 10000, що позначає кількість ящиків. У наступному рядку йде перестановка чисел \{1, 2, \ldots, n\}.
Для кожного тестового випадку виведіть один рядок, що містить – кількість обмінів – за якими слідують рядків, що описують обміни в порядку, в якому вони повинні бути виконані. Один обмін описується двома числами – індексами першого та останнього елемента в інтервалі, що підлягає обміну. Не дотримуйтесь дивного дизайну програмного забезпечення крана – використовуйте стандартну десяткову систему числення.
Приклад 1