L. pi-ip
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Litusiano was lying in the CAMA while looking at a photo of Emilio when he came up with the following problem:

You are given a permutation $$$p$$$ with some elements missing. Your task is to count how many ways you can fill those missing elements such that the result is still a valid permutation, and the permutation $$$q$$$ obtained by the following process:

For each $$$i$$$ from $$$1$$$ to $$$n$$$ (going from left to right), set $$$q[p[i]] = i$$$.

The resulting permutation $$$q$$$ must be the same as the original permutation $$$p$$$.

You are asked to output the value of the count modulo $$$998244353$$$.

Explanation of permutation:

A permutation is an arrangement of a set of elements in a specific order. For example, for the set $$$\{1, 2, 3\}$$$, the following are some permutations:

- $$$[1, 2, 3]$$$ - $$$[2, 1, 3]$$$ - $$$[3, 1, 2]$$$ - $$$[2, 3, 1]$$$

In this problem, a permutation is defined for a sequence of integers from $$$1$$$ to $$$n$$$. The goal is to fill in missing elements in $$$p$$$ in such a way that it remains a valid permutation and satisfies the given condition for $$$q$$$.

Input

Each test case contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2024$$$) — the number of test cases.

For each test case:

- The first line consists of one integer $$$n$$$ ($$$1 \leq n \leq 69 \cdot 10^{4}$$$) — the length of the array $$$a$$$ and the permutation. - The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.

Output

For each test case, output a single integer: the number of ways to fill the missing elements of the permutation $$$p$$$ such that the permutation $$$q$$$ obtained from the process:

For each $$$i$$$ from $$$1$$$ to $$$n$$$ (going from left to right), set $$$q[p[i]] = i$$$,

is the same as the original permutation $$$p$$$. The result should be output modulo $$$998244353$$$.

Example
Input
3
5
1 -1 4 3 -1
3
-1 -1 -1
4
3 -1 4 -1
Output
2
4
0