Mabư Béo là một võ sĩ. Việc luyện tập là điều không thể bỏ qua trong lịch trình hàng ngày của hắn. Hắn có một dàn người máy trong sân tập được tích hợp trí tuệ nhân tạo, có thể đưa ra các đòn đánh gây bất ngờ cho chính hắn.

Mỗi người máy trang bị theo một hoán vị ~p~ từ ~1~ đến ~N~: ~p_1, p_2, \ldots, p_N~. Hoán vị này định nghĩa ngưỡng sức mạnh của nó (cùng với các đòn đánh, bộ kỹ năng nó có, nhưng điều đó không quá quan trọng trong bài toán này).

Công thức tính ngưỡng sức mạnh của một người máy như sau:

Gọi ~p(i)~ là phần tử thứ ~i~ trong hoán vị ~p~ đi theo người máy. Với mọi số nguyên dương ~k~, ta định nghĩa: ~p^1(x) = p(x)~ và ~p^{k+1}(x) = p(p^{k}(x))~. Khi đó: ~p^1(x) = p(x)~, ~p^2(x) = p(p(x))~, ~p^3(x) = p(p(p(x)))~, ... và tương tự với các số lớn hơn.

Ngưỡng sức mạnh của người máy này, thể hiện bằng số ~G(p)~, chính là số nguyên dương bé nhất thỏa mãn: ~p^{G(p)}(x) = x~ với tất cả số nguyên dương ~x \le N~.

Trong một ngày lười biếng, và phải đối đầu với một trong những người máy mạnh nhất trên sân tập của mình, Mabư Béo tự hỏi, làm thế nào để trong nhiều nhất một lần: đổi chỗ hai vị trí ~i~ và ~j~ (~1 \le i < j \le N~, trong hoán vị ~p~, sao cho ngưỡng sức mạnh của người máy là bé nhất có thể.

Vì đáp số có thể rất lớn, hãy in ra chúng, modulo ~998\ 244\ 353~.

Input

Mỗi file test sẽ chứa nhiều trường hợp test. Dòng đầu tiên chứa số trường hợp test ~T~ (~1 \le T \le 1000~). Mô tả một trường hợp test như sau:

Dòng đầu chứa số nguyên ~N~ (~2 \le N \le 10^4~) - số phần tử trong hoán vị.

Dòng thứ hai chứa ~N~ số nguyên: ~p_1, p_2, \ldots, p_N~ (~1 \le p_i \le N~) - hoán vị tương ứng với người máy đang xét đến.

Dữ liệu đảm bảo rằng tổng của ~N~ qua tất cả trường hợp test sẽ không vượt quá ~10^4~.

Output

Với mỗi trường hợp test, in ra một số nguyên duy nhất trên một dòng, thể hiện sức mạnh tối thiểu của người máy sau khi đổi chỗ hai số trong hoán vị của nó. Kết quả cần được in ra, modulo ~998\ 244\ 353~.

Sample Input 1

8
2
1 2
2
2 1
4
2 1 4 3
3
3 2 1
10
2 1 4 5 3 7 8 9 6 10
7
7 1 2 5 4 3 6
3
1 2 3
8
8 1 2 3 4 5 6 7

Sample Output 1

1
1
2
1
4
4
1
4

Notes

Xét trường hợp ví dụ thứ ~5~. Ban đầu, ta chứng minh được ~G(p) = 12~. Ta có thể chọn đổi chỗ ~p(5) = 3~ và ~p(10) = 10~. Khi đó, ~G(p)~ sẽ giảm xuống còn ~4~.