Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in 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. For example, 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 TPGAME to tell the number of inversions for each integer in it.

Input

First line of the input contains t, the number of test cases (1 <= t <= 10). 2 * t lines follow, two for each test case. Each test case begins with an integer N, the number 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