Уэсли Крушер работает ассистентом и ведет курс Введение в Алгоритмы. Во время своего первого занятия студентов попросили придумать свои собственные алгоритмы сортировки. Монти придумал следующий код:

Вдохновленный Карлос предложил следующий код:

Уэсли хочет определить, чей алгоритм лучше.

Для заданного входного массива до 8 значений вычислите и выведите ожидаемое количество итераций для каждого алгоритма. То есть сколько итераций в среднем должен выполнить каждый алгоритм для данного ввода?

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

Первая строка содержит количество тестов t (2 ≤ t ≤ 100). Каждый тест задается в отдельной строке. Первым в строке идет количество элементов в массиве n (2 ≤ n ≤ 8). Затем в строке заданы n целых чисел. Числа лежат в промежутке от 0 до 100 включительно. Элементы массива не обязательно различны.

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

For each test case, print out the expected number of iterations for Monty's algorithm and for Carlos's algorithm, as shown in the sample output section. There should be exactly one space between words and no spaces at the start of each line or at the end of each line. There should be exactly six digits after the decimal point. Rounding should be to nearest representable value.