Problem: Sorting algorithms for sorting data are basic algorithms indispensable in computer science. For example, as shown in the figure below, the operation of "sorting the elements of an array of integer values ​​in ascending order" is alignment.

<image>


Many alignment algorithms have been devised, but one of the basic algorithms is bubble sort. As an example, let's arrange an array of given integer values ​​in ascending order by bubble sort.

<image>



In bubble sort, each calculation step divides the array into "sorted parts" and "unsorted parts". Initially, the entire array will be the unsorted part.

From the beginning of the unsorted part, compare the adjacent elements (green element in the figure) and swap them so that the larger value is to the right. If the two values ​​are equal, they will not be exchanged.

<image>



Repeat this process until the end of the unsorted part (white element in the figure). Finally, add the end to the sorted part (blue element in the figure) to complete one step.

Repeat this step until the unsorted part has a length of 1.

<image>


<image>


<image>



When the length of the unsorted part becomes 1, the sorting process ends.

Now, let's create a program that takes an array of n numbers as input, sorts the numbers in ascending order from the beginning of the array by the above bubble sort procedure, and outputs the number of exchanges of the required array elements. Please give me.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


n
a1
a2
::
an


The first line gives the number n (1 ≤ n ≤ 100), and the following n lines give the i-th number ai (1 ≤ ai ≤ 1000000).

The number of datasets does not exceed 20.

Output

Outputs the number of data element exchanges (integer) for each data set on one line.

Example

Input

5
5
3
2
1
4
6
1
2
3
4
5
6
3
3
2
1
0


Output

7
0
3

Solution (in JAVA):

Solution:

import java.awt.geom.Point2D;
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Scanner;

import javax.xml.crypto.Data;
public class Main {

	static PrintWriter out = new PrintWriter(System.out);
	static FastScanner sc = new FastScanner();
	static Scanner stdIn = new Scanner(System.in);
	static int count = 0;
	public static void main(String[] args) {
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			count = 0;
			int[] list = new int[n];
			for(int i = 0; i < n; i++) {
				list[i] = sc.nextInt();
			}
			
			bubbleSort(list);
			
			out.println(count);
		}
		out.flush();
	}
	
	public static void bubbleSort(int[] a) {
		for(int i = a.length; i>= 0; i--) {
			for(int j = 1; j < i; j++) {
				if(a[j] < a[j-1]) {
					swap(a,j,j-1);
				}
			}
		}
	}
	
	public static void swap(int[] a, int b, int c) {
		count++;
		int t = a[b];
		a[b] = a[c];
		a[c] = t;
	}

}
		
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
    

}