G. Link with Limit
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Link has a function $$$f(x)$$$, where $$$x$$$ and $$$f(x)$$$ are both integers in $$$[1,n]$$$.

Let $$$f_n(x)=f(f_{n-1}(x))$$$ and $$$f_1(x) = f(x)$$$, he define the power of a number $$$x$$$ as: $$$$$$g(x) = \lim \limits_{n \to + \infty} \frac{1}{n} \sum_{i=1}^{n} f_i(x)$$$$$$

He wants to know whether $$$x$$$ has the same power for all $$$x \in [1,n]$$$.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 100$$$) – the number of test cases.

For each test case:

In the first line, there is an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

In the second line, there are $$$n$$$ integers, the $$$i$$$-th integer shows the value of $$$f(i)$$$ ($$$1 \leq f(i) \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^6$$$.

Output

For each test case, output 'YES' if all $$$x$$$ have the same power. Otherwise, output 'NO'.

Example
Input
2
2
1 2
2
1 1
Output
NO
YES