A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1, 2, 3} can be deranged into {2, 3, 1} and {3, 1, 2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1, 1, 2, 2, 3} could be deranged into {2, 2, 1, 3, 1}, {2, 2, 3, 1, 1}, {2, 3, 1, 1, 2}, and {3, 2, 1, 1, 2}.

Input

First line contains T (1 <= T <= 100) the number of test cases. Each test case contains two lines. First line contains an integer N (1 <= N <= 15) denoting total number of elements in the array. Second line contains a space separated list of N integers Ai such that 0 <= Ai < N.

Output

For each test case output an integer, the total number of derangements of the array.

Example

Input:
2
5
1 1 2 2 3
6
0 0 0 1 1 1

Output:
4
1