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