열차 차량 재정렬

오래된 기차역에 가면 마지막까지 남아 있는 "차량 교환원" 중 한 명을 아직도 만날 수 있습니다. 차량 교환원은 기차의 차량 순서를 다시 배열하는 일만 하는 철도 직원입니다.

차량이 알맞은 순서로 정렬되면, 기관사는 각 화물이 향하는 역에서 차량을 하나씩 떼어 놓기만 하면 됩니다.

"차량 교환원"이라는 이름은 이 일을 처음 한 사람에게서 유래했습니다. 그는 철교 옆 역에서 일했는데, 이 다리는 위로 열리는 대신 강 한가운데 기둥을 축으로 회전했습니다. 90도 회전하면 배가 양옆으로 지나갈 수 있었습니다. 첫 번째 차량 교환원은 이 다리 위에 차량을 최대 두 대까지 올려 조작할 수 있음을 발견했습니다. 다리를 180도 돌리면 그 두 차량의 자리가 서로 바뀌어 기차를 다시 배열할 수 있었습니다. (그 결과 차량의 방향이 반대가 되지만, 차량은 어느 방향으로도 잘 달리므로 상관없습니다.)

이제 차량 교환원이 거의 사라졌기에, 철도 회사는 이 작업을 자동화하려 합니다. 프로그램의 일부는 주어진 기차에 대해 인접한 두 차량을 교환하는 연산을 최소 몇 번 해야 기차를 정렬할 수 있는지 판단해야 합니다. 순열을 정렬하는 데 필요한 인접 교환의 최소 횟수는 그 순열의 반전(inversion) 수, 즉 현재 서로 잘못된 순서로 놓인 차량 쌍의 개수와 같습니다.

질문:

1. 기차 $T$에 대해 $m[T]$를 $T$를 정렬하는 데 필요한 최소 교환 횟수라고 합시다. 차량이 $L$개인 기차에서 $m[T]$가 가질 수 있는 가장 큰 값은 무엇일까요? (기차가 완전히 뒤집혀 있을 때 도달하는 $L(L-1)/2$입니다.)
2. 아래 명세를 만족하는 프로그램을 작성하세요.

첫 번째 줄에 테스트 케이스의 수 $N$이 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다.

• 첫 번째 줄에는 기차의 길이를 나타내는 정수 $L$이 주어집니다 ($0 \le L \le 50$).
• 두 번째 줄에는 $1$부터 $L$까지의 수를 한 번씩 포함하는 순열이 주어지며, 이는 차량의 현재 순서를 나타냅니다. 차량은 $1$번이 맨 앞, 그다음 $2$번, 이렇게 이어져 $L$번이 맨 뒤에 오도록 정렬되어야 합니다.

각 테스트 케이스마다 다음 문장을 출력하세요.

Optimal train swapping takes S swaps.

여기서 $S$는 그 기차를 정렬하는 데 필요한 최소 교환 횟수입니다.