There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town¡¯s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people¡¯s life more convenient (especially for who forget to take a device).
Tina and Town were playing a game on this stone. First, a permutation of numbers from $1$ to $n$ were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,¡±Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn¡¯t know the answer so she asked you to find out the answer for her.
Since the answer may be very large, you only need to output the answer modulo $3*{2}^{30}+1=3221225473$ (a prime).
Input
The first line is an integer $T$ representing the number of test cases. $ T \leq 5$
For each test case, the first line is an integer $n$ representing the length of permutation. $ n \leq 3*{10}^{6} $
The second line contains $n$ integers representing a permutation $A_1...A_n$. It is guaranteed that numbers are different each other and all $A_i$ satisfies ( $1 \leq A_i \leq n$ ).
Output
For each test case, print a number $ans$ representing the answer.
