크러셔의 코드

웨슬리 크러셔는 알고리즘 입문 수업의 조교다. 첫 수업에서 생도들은 각자 정렬 알고리즘을 하나씩 만들어 오라는 과제를 받았다. 몬티가 만든 코드는 다음과 같다.

while (!sorted(a)) {
    int i = random(n) ;
    int j = random(n) ;
    if (a[min(i,j)] > a[max(i,j)])
        swap(a[i], a[j]) ;
}

여기에 자극을 받은 카를로스는 다음 코드를 만들었다.

while (!sorted(a)) {
    int i = random(n-1) ;
    int j = i + 1 ;
    if (a[i] > a[j])
        swap(a[i], a[j]) ;
}

배열 a는 원소가 $N$개이고 번호는 0번부터 $N-1$번까지이며, 코드에 나오는 n이 이 $N$이다. random(k)는 호출할 때마다 0 이상 $k$ 미만의 정수 하나를 독립적으로, 모두 같은 확률로 고른다. 반복 횟수는 while 문의 본문을 실행한 횟수다. 두 값을 비교만 하고 교환하지 않은 경우도 한 번으로 센다. 처음부터 정렬되어 있는 배열은 본문에 들어가지 않으므로 반복 횟수가 0이다.

웨슬리는 두 알고리즘 중 어느 쪽이 나은지 판단해야 한다. 원소가 최대 8개인 배열이 주어질 때, 각 알고리즘이 그 배열을 정렬할 때까지 실행하는 반복 횟수의 기댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($2 \le T \le 100$)

각 테스트 케이스는 한 줄로 주어진다. 줄의 첫 값은 배열의 원소 개수 $N$이고 ($2 \le N \le 8$), 그 뒤에 배열의 원소 $N$개가 공백으로 구분되어 주어진다. 각 원소는 0 이상 100 이하의 정수이며, 같은 값이 여러 번 나올 수 있다.

각 테스트 케이스마다 몬티의 알고리즘과 카를로스의 알고리즘이 실행하는 반복 횟수의 기댓값을 Monty <몬티의 기댓값> Carlos <카를로스의 기댓값> 형식으로 한 줄에 출력한다.

두 기댓값 모두 소수점 아래 여섯 자리까지, 일곱째 자리에서 반올림해 출력한다. 단어 사이에는 공백을 정확히 하나만 두고, 줄의 처음과 끝에는 공백을 두지 않는다. 어떤 답도 반올림 경계에서 $10^{-9}$ 이내로 가깝지 않으므로, 경계를 어느 쪽으로 처리하든 출력하는 숫자는 같다.