1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 299 - Train Swapping
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=235
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Sorting - Insertion sort
* Status : Accepted
* Runtime: 0.132
*/

import java.io.*;
import java.util.*;

class Main {

public static void main(String...args)
{
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
int n,swaps;
for(int c = 0; c < testCases; c++)
{
n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++)
a[i] = sc.nextInt();

swaps = 0;

for(int i = 0; i < n-1; i++)
{
int j = i;
while(j >= 0 && a[j] > a[j+1])
{
a[j] = a[j] ^ a[j+1];
a[j+1] = a[j] ^ a[j+1];
a[j] = a[j] ^ a[j+1];
j--;
swaps++;
}
//System.out.println( + " " + Arrays.toString(a));
}
System.out.printf("Optimal train swapping takes %d swaps.\n", swaps);

}
}
}