I grip my troubles within my hand, then hurl them off a thousand lands.

— SHUN, ONMYWAY

Consider that Simons is given an array $$$a$$$ of size $$$m$$$.

Simons must operate on the array exactly once as follows:

First, he has to select an integer $$$k$$$ and choose $$$k$$$ pairs of integers $$$[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$$$, such that:
- $$$l_i\le r_i$$$ for each $$$1\le i\le k$$$,
- $$$l_1=1$$$, $$$r_k=m$$$, and
- $$$r_i+1=l_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.
Then, he reverses each subarray $$$[a_{l_i},a_{l_i+1},\ldots, a_{r_i}]$$$ independently. After this, the array will become $$$[a_{r_1},a_{r_1-1},\ldots,a_{l_1},a_{r_2},\ldots,a_{l_{k-1}},a_{r_{k}},a_{r_k-1},\ldots,a_{l_k}]$$$.

You are given an array $$$T$$$ of size $$$n$$$. Count the number of arrays $$$S$$$ such that Simons can transform $$$S$$$ to $$$T$$$, modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 8000$$$). The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1\le n\le 8000$$$) — the length of $$$T$$$.

The second line contains $$$n$$$ integers $$$T_1,T_2,\ldots,T_n$$$ ($$$1\le T_i\le 8000$$$) — the elements of $$$T$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$8000$$$.

Output

For each test case, output a single integer — the number of arrays $$$S$$$, modulo $$$998\,244\,353$$$.

Note

In the first test case, we can see only the following arrays can be transformed to $$$T$$$:

For $$$S=[2,1,1,1]$$$, Simons will choose $$$[1,3]$$$ and $$$[4,4]$$$. Thus, the array will become $$$[1,1,2,1]$$$, equal to $$$T$$$.
For $$$S=[1,2,1,1]$$$, Simons will choose $$$[1,4]$$$.
For $$$S=[1,1,2,1]$$$, Simons will choose $$$[1,2]$$$, $$$[3,3]$$$, and $$$[4,4]$$$.
For $$$S=[1,1,1,2]$$$, Simons will choose $$$[1,2]$$$ and $$$[3,4]$$$.

In the second test case, we can see only the following arrays can be transformed to $$$T$$$:

For $$$S=[1,1,3,2]$$$, Simons will choose $$$[1,1]$$$ and $$$[2,4]$$$.
For $$$S=[1,2,1,3]$$$, Simons will choose $$$[1,1]$$$, $$$[2,2]$$$, and $$$[3,4]$$$.
For $$$S=[1,2,3,1]$$$, Simons will choose $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,3]$$$, and $$$[4,4]$$$.
For $$$S=[1,3,2,1]$$$, Simons will choose $$$[1,4]$$$.
For $$$S=[2,1,1,3]$$$, Simons will choose $$$[1,2]$$$ and $$$[3,4]$$$.
For $$$S=[2,1,3,1]$$$, Simons will choose $$$[1,2]$$$, $$$[3,3]$$$, and $$$[4,4]$$$.
For $$$S=[3,2,1,1]$$$, Simons will choose $$$[1,3]$$$ and $$$[4,4]$$$.

Simons and Dividing the Rhythm

Examples