For a permutation $P = (p_1, p_2, \dots, p_n)$ of length $n$ and an integer $k \ge 0$, the $k$-th power of $P$ is defined as $P^{(k)} = (p_1^{(k)}, p_2^{(k)}, \dots, p_n^{(k)})$, where the $i$-th term of the permutation is: $$p_i^{(k)} = \begin{cases} i, & k = 0, \\ p_{p_i^{(k-1)}}^{(k-1)}, & k > 0. \end{cases}$$ It is easy to prove that any power of any permutation is also a permutation. Define the cycle value $v(P)$ of a permutation $P$ as the smallest positive integer $k$ such that $P^{(k+1)} = P$.

Given a permutation $A = (a_1, a_2, \dots, a_n)$ of length $n$, for integers $1 \le i, j \le n$, define $f(i, j)$: If there exists $k \ge 0$ such that $a_i^{(k)} = j$, then $f(i, j) = 0$. Otherwise, let $A_{ij}$ be the permutation obtained by swapping the $i$-th term $a_i$ and the $j$-th term $a_j$ of $A$, then $f(i, j) = v(A_{ij})$.

Calculate the value of $\sum_{i=1}^n \sum_{j=1}^n f(i, j)$. The answer may be very large, so you only need to output the result modulo $(10^9 + 7)$.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. For each test case, the first line contains a positive integer $n$, representing the length of the permutation. The next line contains $n$ integers $a_1, a_2, \dots, a_n$, describing the input permutation.

Output

For each test case, output a single integer on a single line, representing the result of the required answer modulo $(10^9 + 7)$.

Examples

Input 1

2
3
1 2 3
3
2 3 1

Output 1

12
0

Note

For the first test case, $f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$, and all other $f(i, j)$ are $0$. For the second test case, all $f(i, j)$ are $0$.

Input 2

(See perm/perm2.in in the contestant directory)

Output 2

(See perm/perm2.ans in the contestant directory)

Note

In this set of examples, the first test case satisfies $n \le 35$, the first four test cases satisfy $n \le 200$, and all test cases satisfy $n \le 2500$.

Input 3

(See perm/perm3.in in the contestant directory)

Output 3

(See perm/perm3.ans in the contestant directory)

Note

In this set of examples, the first test case satisfies special property A, the second test case satisfies special property B, the third test case satisfies special property C, the first four test cases satisfy $n \le 10^5$, and the fifth test case satisfies $n \le 5 \times 10^5$.

Subtasks

For 100% of the test data, $1 \le T \le 5$, $1 \le n \le 5 \times 10^5$, $1 \le a_i \le n$.

The test cases are categorized as follows:

• Test cases 1-2: $n \le 10^5$, satisfy special property A.
• Test case 3: $n \le 35$.
• Test case 4: $n \le 200$.
• Test case 5: $n \le 2500$.
• Test case 6: $n \le 10^5$, satisfies special property B.
• Test case 7: $n \le 10^5$, satisfies special property C.
• Test case 8: $n \le 10^5$.
• Test cases 9-10: $n \le 5 \times 10^5$.

Special property A: $a_i = (i \pmod n) + 1$. Special property B: For any $1 \le i \le n$, there exists $1 \le k \le 20$ such that $a_i^{(k)} = i$. Special property C: There exists a set $S$ with size at most $10$ such that for any $1 \le i \le n$, there exist $x \in S, k \ge 0$ such that $a_x^{(k)} = i$.

The input data scale is large; please use a fast input method.