Солітер
У вас є колода з N карт, пронумерованих від 1 до N. Гра починається з картами, що лежать обличчям вниз у "початковому" місці. Є також три інші місця, де ви можете грати своїми картами обличчям вгору (якщо вони вже обличчям вгору на вершині будь-якої з інших стопок): "ціль", "допоміжна" та "стопка". Ви виграєте гру, коли всі карти розміщені на цілі у зростаючому порядку (N зверху). Правила:
Ви можете грати карти на "ціль" лише якщо значення верхньої карти "цілі" на одиницю менше, ніж значення карти, яку ви намагаєтеся розмістити (якщо "ціль" порожня, ви можете розмістити там лише карту зі значенням 1). Наприклад, якщо верхня карта в "цілі" 3, ви можете розмістити лише 4 на "ціль".
Ви можете грати карти на "допоміжну" лише якщо значення верхньої карти "допоміжної" на одиницю більше, ніж значення карти, яку ви намагаєтеся розмістити (якщо "допоміжна" порожня, ви можете розмістити там лише карту зі значенням N). Наприклад, якщо верхня карта в "допоміжній" 8, ви можете розмістити лише 7 на "допоміжну".
Ви можете перемістити карту на "стопку" лише з верхньої частини "початкової" колоди, перевернувши цю карту (пам'ятаєте? карти в початковій колоді лежать обличчям вниз).
Коли всі карти обличчям вгору ("початкова" колода порожня) і якщо гра ще не закінчена, візьміть карти зі "стопки" і переверніть всі їх на "початкову" позицію. Це буде ваша нова "початкова колода". Щоб уточнити - верхня карта в "стопці" (обличчям вгору) стане нижньою картою в "початковій" (обличчям вниз).
Яка мінімальна кількість ходів типу 4 вам потрібна, щоб завершити гру?
Вхідні дані
Перший рядок входу містить ціле число T (1 ≤ T ≤ 100) - кількість тестових випадків. Кожен тестовий випадок складається з двох рядків:
Перший рядок містить ціле число N (1 ≤ N ≤ 1000).
Другий рядок містить опис "початкової" колоди. Перше число - це значення карти на дні початкової колоди, що лежить обличчям вниз (отже, остання карта буде зіграна першою на "стопку"). Це буде перестановка списку цілих чисел від 1 до N.
Вихідні дані
Для кожного тестового випадку виведіть мінімальну кількість ходів типу 4, які вам потрібні, щоб "виграти" гру, на окремому рядку.