NOVICE65 - Derangements HARD

no tags 

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

hide comments
Stanislav Zholnin: 2015-09-25 20:16:37

I think it's quite general mathematical problem - easily can be just coincidence.

Prasanth: 2014-09-22 15:12:10

This is a problem from TopCoder SRM 176

Last edit: 2014-09-22 15:12:25
Yongwhan Lim: 2012-02-16 11:06:15

there should be a source for this problem: TopCoder SRM.

EDIT: Which one? And if so, they don't exactly permit usage of their problems elsewhere.

Last edit: 2012-03-29 06:04:57

Added by:amit karmakar
Date:2011-07-01
Time limit:0.402s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64