9615: Love Wins All

It's a loving community!

There are $n$ residents in the community, and each resident $i(1\le i\le n)$ in the community has a unique resident a_i (1≤i≤n) in the community whom he/she loves so much. Each two residents love different residents. A resident can love himself / herself. It is guaranteed that $n$ is even.

One day, a bad thing happens: They need to choose $2$ residents to be forbidden to get married forever.

And to prevent such a thing from happening in the future, the rest $n-2$ residents decide to get married as n/2−1 couples, each couple consisting of $2$ persons (of course). It makes no sense that a couple consists of resident $x$ and resident $y$ while neither $x$ loves $y$ nor $y$ loves $x$, so such a thing never happens.

• In one plan, a person $i$ is married, and in the other, he/she is not.
• In one plan, a person $i$ is married to $j$, and in the other, he/she is not married to $j$.

Each test contains multiple test cases. The first line contains the number of test cases T (1≤T≤10⁴) .
Each test case consists of two lines.
The first line contains $1$ integer n (4≤n≤5×10⁵), the number of residents in the community. It's guaranteed that $n$ is even.
The second line contains $n$ integers a₁,a₂,…,a_n (1≤a_i≤n), where a_i represents the one that the resident $i$ loves. It is guaranteed that if i=j (1≤i,j≤n), a_i=a_j .
It is guaranteed that ∑n over all test cases in one test will not exceed 5×10⁵ .

For each test case, output $1$ integer: the number of different marriage plans modulo $998244353$.