POLSKI SPOJ

Jasio za dobre sprawowanie został przydzielony do bardziej zobowiązujących działań. Jak zwykle szef w czasie przerwy wymyślił mu kolejny ciekawy problem.

Mając N listów zaadresowanych do pewnych osób, na ile sposobów można włożyć listy do kopert tak, aby żaden list nie znalazł się we właściwej kopercie?

Input

Liczba T <= 200 jako liczba testów.
Każdy test rozpoczyna się liczbą 1<=N<=15, czyli ilość listów do wysłania.
W kolejnym wierszu N liczb, odpowiadających, do którego adresata dany list jest skierowany. Każda liczba jest mniejsza od N ( indeksujemy listy od 0 )

Output

Dla każdego testu w oddzielnej linii liczba możliwości.

Example

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