Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in http://www.spoj.com/problems/TPGAME/ (though with a little help from your side), it was my turn to ask him a question. This would again be a coding question as you might be knowing he is a noob in coding. I gave him a permutation of N distinct integers from 1...N and asked him the rank of the permutation when all possible permutations of the integers are arranged lexicographically. eg for N=3, all possible permutations arranged lexicographically would be:-

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

From the above, rank of 1 2 3 would be 1, rank of 1 3 2 would be 2 and so on...

HELP HIM!

NOTE:- You may assume it is the same permutation which Blackhood gave him in http://www.spoj.com/problems/TPGAME/ to tell the no. of inversions for each integer in it.

Input

First line of the input contains t, the no. of test cases. (1<=t<=10)

2*t lines follow, two for each test case.

Each test case begins with an integer N , the no of elements in the permutation.(1<=N<=200000)

The next line contains N space separated distinct integers from 1...N,  representing the permutation.

Output

For each test case, print the rank of permutation %1000000007 on a new line.

Example

Input:
3
1
1
3
3 2 1
4
2 1 4 3

Output:
1
6
8