Lightoj 1166

Given an array containing a permutation of 1 to n, you have to find the minimum number of swaps to sort the array in ascending order. A swap means, you can exchange any two elements of the array.

For example, let n = 4, and the array be 4 2 3 1, then you can sort it in ascending order in just 1 swaps (by swapping 4 and 1).

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two lines, the first line contains an integer n (1 ≤ n ≤ 100). The next line contains n integers separated by spaces. You may assume that the array will always contain a permutation of 1 to n.

Output

For each case, print the case number and the minimum number of swaps required to sort the array in ascending order.

Sample Input

Output for Sample Input

4 2 3 1

4 3 2 1

1 2 3 4

Case 1: 1

Case 2: 2

Case 3: 0

#include <iostream>
#include <stdio.h>
using namespace std;
int a[10000];
int main() {
    int t, n;
    cin >> t;
    for(int k = 1; k <= t; ++k) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >>a[i];
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int x = i;
            int cnt = 0;
            while (a[i] != i) {
                x = a[i];
                swap(a[x], a[i]);
                cnt++;
            }
            ans += cnt;
        }
        printf("Case %d: %d
",k, ans);
    }
    return 0;
}