Brainman

Raymond Babbitt은 형제 Charlie를 놀라게 한다. 최근 그는 바닥에 흩어진 이쑤시개 246개를 한눈에 순식간에 세었고, 트럼프 카드까지 셀 수 있다. Charlie도 그런 멋진 일을 해내 형을 이기고 싶어 한다.

Charlie가 생각해 낸 과제는 이렇다. $N$개의 수로 이루어진 수열이 주어진다. 목표는 수들을 옮겨서 수열을 비내림차순으로 정렬하는 것이다. 허용되는 연산은 인접한 두 수를 서로 바꾸는 것뿐이다.

예를 들어 수열 $(2\ 8\ 0\ 3)$은 인접한 수를 아홉 번 바꿔 정렬할 수 있다.

하지만 단 세 번의 인접 교환만으로도 정렬할 수 있다.

질문은 이것이다. 주어진 수열을 정렬하는 데 필요한 인접 교환의 최소 횟수는 얼마인가? Charlie는 Raymond와 같은 암산 능력이 없으므로, 이 질문에 답하는 프로그램을 대신 작성해 달라고 부탁한다.

첫째 줄에 시나리오의 개수가 주어진다.

각 시나리오는 한 줄로 주어진다. 먼저 수열의 길이 $N$ ($1 \le N \le 1000$)이 주어지고, 이어서 수열의 원소 $N$개가 주어진다(각 원소는 $[-1000000, 1000000]$ 범위의 정수이다). 한 줄의 모든 수는 공백 하나로 구분된다.

각 시나리오마다 Scenario #i: 형식의 줄을 출력한다. 여기서 i는 1부터 시작하는 시나리오 번호이다. 이어서 다음 줄에 해당 수열을 정렬하는 데 필요한 인접 교환의 최소 횟수를 출력한다. 연속한 두 시나리오의 출력 사이에는 빈 줄 하나를 넣는다.