Солитер
У вас есть колода из N карт, пронумерованных от 1 до N. Игра начинается с карт, лежащих рубашкой вверх в "начальном" месте. Также есть три других места, где вы можете играть карты лицом вверх (как только они окажутся лицом вверх на вершине любой из других стопок): "цель", "помощник" и "стопка". Вы выигрываете игру, когда все карты размещены на "цели" в порядке возрастания (N сверху). Правила:
Вы можете играть карты на "цель" только если значение верхней карты "цели" на единицу меньше значения карты, которую вы пытаетесь положить (если "цель" пуста, вы можете положить туда только карту со значением 1). Например, если верхняя карта в "цели" 3, вы можете положить только 4 на "цель".
Вы можете играть карты на "помощник" только если значение верхней карты "помощника" на единицу больше значения карты, которую вы пытаетесь положить (если "помощник" пуст, вы можете положить туда только карту со значением N). Например, если верхняя карта в "помощнике" 8, вы можете положить только 7 на "помощник".
Вы можете перемещать карту на "стопку" только с вершины "начальной" колоды, перевернув эту карту (помните, карты в начальной колоде лежат рубашкой вверх).
Как только все карты окажутся лицом вверх (начальная колода пуста) и если игра еще не закончена, возьмите карты из "стопки" и переверните их все на "начальное" место. Это будет ваша новая "начальная колода". Для ясности - верхняя карта в "стопке" (лицом вверх) станет нижней картой в "начальной" (лицом вниз).
Какое минимальное количество ходов типа 4 вам нужно, чтобы закончить игру?
Входные данные
Первая строка входных данных содержит целое число T (1 ≤ T ≤ 100) - количество тестов. Каждый тест состоит из двух строк:
Первая строка содержит целое число N (1 ≤ N ≤ 1000).
Вторая строка содержит описание "начальной" колоды. Первое число - это значение карты на дне начальной колоды, лежащей рубашкой вверх (так что последняя карта будет сыграна первой на "стопку"). Это будет перестановка списка целых чисел от 1 до N.
Выходные данные
Для каждого теста выведите минимальное количество ходов типа 4, необходимых для "выигрыша" игры в отдельной строке.