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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def bubble_sort(n):
	arr = [int(input()) for _ in range(n)]
	cnt = 0
	for i in range(n):
		for j in range(n - 1, i, -1):
			if arr[j] < arr[j - 1]:
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
				cnt += 1
	return cnt
while True:
	n = int(input())
	if n == 0:
		break
	print(bubble_sort(n))


def b_sort(lst):
	limit = len(lst) - 1
	cnt = 0
	while limit:
		for i in range(limit):
			if lst[i] > lst[i + 1]:
				(lst[i], lst[i + 1]) = (lst[i + 1], lst[i])
				cnt += 1
		limit -= 1
	return cnt
while True:
	n = int(input())
	if n == 0:
		break
	alst = []
	for _ in range(n):
		alst.append(int(input()))
	print(b_sort(alst))


def bubble_sort(item_list):
	length = len(item_list)
	count = 0
	for lp in range(length):
		for lp2 in range(length - lp - 1):
			if item_list[lp2] > item_list[lp2 + 1]:
				tmp = item_list[lp2]
				item_list[lp2] = item_list[lp2 + 1]
				item_list[lp2 + 1] = tmp
				count += 1
	return count
while True:
	input_count = int(input())
	if input_count == 0:
		break
	data = [int(input()) for _ in range(input_count)]
	result = bubble_sort(data)
	print(result)


import math
import fractions
import heapq
import collections
import re
import array
import bisect
from collections import Counter, defaultdict

class BIT(object):

	def __init__(self, size):
		self.size = size
		self.l = [0] * (size + 1)

	def sum(self, i):
		r = 0
		while i > 0:
			r += self.l[i]
			i -= i & -i
		return r

	def add(self, i, x):
		while i <= self.size:
			self.l[i] += x
			i += i & -i
max_a = 1000000

def solve(a):
	bit = BIT(max_a)
	ans = 0
	for (i, x) in enumerate(a):
		ans += i - bit.sum(x)
		bit.add(x, 1)
	return ans

def main():
	while True:
		N = int(input())
		if N == 0:
			return
		a = []
		for i in range(N):
			a.append(int(input()))
		print(solve(a))
main()


while 1:
	n = int(input())
	if n == 0:
		break
	alist = []
	for _ in range(n):
		a = int(input())
		alist.append(a)
	cnt = 0
	for i in range(len(alist)):
		for j in range(len(alist) - 1, i, -1):
			if alist[j] < alist[j - 1]:
				(alist[j], alist[j - 1]) = (alist[j - 1], alist[j])
				cnt += 1
	print(cnt)


def solve(A):
	res = 0
	right = len(A)
	while right != 0:
		for left in range(0, right):
			if left + 1 < len(A) and A[left] > A[left + 1]:
				(A[left], A[left + 1]) = (A[left + 1], A[left])
				res += 1
		right -= 1
	return res
while True:
	n = int(input())
	if n == 0:
		break
	A = [int(input()) for i in range(n)]
	print(solve(A))


while True:
	n = int(input())
	if n == 0:
		break
	a = [0] * 105
	for i in range(n):
		a[i] = int(input())
	cnt = 0
	for i in range(n - 1, 0, -1):
		for j in range(i):
			if a[j] > a[j + 1]:
				cnt += 1
				(a[j], a[j + 1]) = (a[j + 1], a[j])
	print(cnt)


while True:
	N = int(input())
	if N == 0:
		break
	a = []
	cnt = 0
	for l in range(N):
		a.append(int(input()))
	for i in range(N - 1, 0, -1):
		for j in range(i):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
				cnt += 1
	print(cnt)


while True:
	n = int(input())
	A = []
	if n == 0:
		break
	for i in range(n):
		num = int(input())
		A.append(num)
	cnt = 0
	for i in range(n):
		for j in range(n - 1, 0, -1):
			if A[j] < A[j - 1]:
				(A[j], A[j - 1]) = (A[j - 1], A[j])
				cnt += 1
	print(cnt)


while True:
	n = int(input())
	if n == 0:
		break
	Num_lis = []
	cou = 0
	for i in range(n):
		Num_lis.append(int(input()))
	S_lis = sorted(Num_lis)
	while Num_lis != S_lis:
		for j in range(n - 1):
			if Num_lis[j] > Num_lis[j + 1]:
				(Num_lis[j], Num_lis[j + 1]) = (Num_lis[j + 1], Num_lis[j])
				cou += 1
	print(cou)


while 1:
	n = int(input())
	if n == 0:
		break
	c = 0
	a = [int(input()) for _ in range(n)]
	for i in range(n):
		for j in range(n - 1, 0, -1):
			if a[j] < a[j - 1]:
				(c, (a[j], a[j - 1])) = (c + 1, (a[j - 1], a[j]))
	print(c)


import sys, math, os, bisect
PYDEV = os.environ.get('PYDEV')
if PYDEV == 'True':
	sys.stdin = open('sample-input.txt', 'rt')

def bubble_sort(N, A):
	cnt = 0
	last = N - 1
	while last > 0:
		for k in range(last):
			if A[k] > A[k + 1]:
				(A[k], A[k + 1]) = (A[k + 1], A[k])
				cnt += 1
		last -= 1
	return cnt
while True:
	N = int(input())
	if N == 0:
		break
	A = [int(input()) for _ in range(N)]
	print(bubble_sort(N, A))


def bs(v):
	nc = 0
	m = len(v)
	while m > 0:
		j = 0
		while j < m - 1:
			if v[j] > v[j + 1]:
				x = v[j + 1]
				v[j + 1] = v[j]
				v[j] = x
				nc += 1
			j += 1
		m -= 1
	return nc
while True:
	n = int(input())
	if n == 0:
		break
	v = []
	for _ in range(n):
		x = int(input())
		v.append(x)
	print(bs(v))


while True:
	n = int(input())
	if n == 0:
		break
	a = [int(input()) for _ in range(n)]
	count = 0
	for i in range(n):
		for j in range(n)[:0:-1]:
			if a[j] < a[j - 1]:
				(a[j], a[j - 1]) = (a[j - 1], a[j])
				count += 1
	print(count)


def bubbleSort(list):
	j = len(list) - 1
	bcnt = 0
	while j:
		for i in range(j):
			if list[i] > list[i + 1]:
				(list[i], list[i + 1]) = (list[i + 1], list[i])
				bcnt += 1
		j -= 1
	return bcnt
while True:
	n = int(input())
	if n == 0:
		break
	A = []
	for _ in range(n):
		A.append(int(input()))
	print(bubbleSort(A))


while True:
	n = int(input())
	if n == 0:
		break
	L = []
	for _ in range(n):
		L.append(int(input()))
	cnt = 0
	for k in range(1, len(L))[::-1]:
		for i in range(k):
			if L[i + 1] < L[i]:
				cnt += 1
				(L[i + 1], L[i]) = (L[i], L[i + 1])
	print(cnt)