Пиратские катакомбы на острове Сокровищ были вырыты по следующему принципу. После скрытого входа расположена пещера, из которой выходят два туннеля – налево и направо. Каждый из туннелей заканчивается пещерой, из которой так же выходит два туннеля, и т.д. Длина каждого туннеля равна единице. Конечные пещеры, которые находятся на расстоянии D от входа, не имеют дальнейших выходов. Никакие туннели между собой не пересекаются, и не ведут к одной пещере. Число D называют глубиной катакомб.

   В каждой из конечных пещер спрятан один сундук с сокровищами. Перед прибытием на остров Капитана Джека Воробья пираты решили переместить эти сундуки в соответствии с последними указаниями Капитана. Пираты нарисовали план катакомб и пронумеровали конечные пещеры слева направо. Потом для каждого сокровища был установлен номер пещеры, в которой он должен оказаться перед прибытием Капитана. После перемещения в каждой пещере снова окажется только один сундук.

   Чтобы обеспечить безопасность сокровищ, пираты могут только обменивать между собой сундуки из двух пещер. Только после окончания одного обмена можно начинать другой. Необходимо найти наименьшее суммарное расстояние, которое пиратам необходимо будет нести сундуки, чтобы разместить их требуемым образом.

   Входные данные

   Первая строка входного файла содержит одно целое число T – номер теста (1 ≤ T ≤ 11). В кождом тесте первая строка содержит одно целое число D – глубину катакомб (D ≤ 8).

   Вторая строка содержит 2^D разных целых чисел от 1 до 2^D. Каждое i-ое из них идентифицирует номер пещеры, в которую должен попасть сундук, находившийся сначала в пещере i.

   Выходные данные

   Первая строка выходного файла должна содержать единственное целое число – минимальное суммарное расстояние, которое пройдут пираты с сокровищами. Вторая строка: целое число K – соответствующее количество обменов.