3479：Code

A new code system was designed recently. It works in the following way:
The original code A is a linear sequence containing N elements. Each element is an integer between 1 and N. At first the code system will generate a permutation B of length N automatically. Compare sequence A and B we can compute a hidden code C by the following rule:



where, B^-1₁ stands for the location of integer i in permutation B. For example, if B = {3, 1, 2}, we have B^-1₁=2,B^-1₃=1 .
The code system has many great advantages in security. For instance, hackers will not have any idea about the original code A if he only gets the hidden code C. Considering all of these, we ordered one of the code systems.
However, some awful thing happened yesterday, the boss totally forgot his original code! The boss has the record of his hidden code, and he wants to ask you if it’s possible for him to find the original code soon.
More exactly, your task is to count the number of possible original codes that may generate the hidden code C by some permutation B.

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For each test case there will be two lines. The first line contains one integer N (≤ 30) which is the length of the hidden code C. The second line contains N integers between 1 and N giving C.

For each test case, output one line containing exactly one integer, the number of different original codes that may generate C. Take a look at the sample output for format.