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