Given a permutation of the first N (0 < N < 20) natural numbers, find the lexicographic number of the permutation. For example, if N = 3, then :
Rank    Permutation
1    1 2 3
2    1 3 2
3    2 1 3
4    2 3 1
5    3 1 2
6    3 2 1
 
Input:  
The first line consists of the number of test cases T (T <= 10000). Each test case consists of 2 lines- the first line has an integer N, the length of the permuatation, and the second line consists of a permutation of the integers from 1, 2, ... , N
 
Output:
For each test case, output 1 integer, the rank of the permutation. Print each answer on a new line.
It is guaranteed that the result will fit in a 64-bit signed integer.
 
example:
Input:
1
4
2 1 4 3
 
output:
8