Trước khi thực hiện nhiệm vụ cuối cùng, Chtholly hỏi Willem ba câu hỏi. Câu hỏi thứ ba là: khi hồi kết cuối cùng cũng đến, ai sẽ còn lại để chứng kiến nó? Willem không thể trả lời trực tiếp. Thay vào đó, anh vẽ một vòng tròn lên bảng, gọi đó là vòng tròn của vạn vật, và viết xuống \(n\) số nguyên được đánh nhãn \(a_1,a_2,\ldots,a_n\).

Mỗi cách sắp xếp các số quanh vòng tròn tương ứng với một cách khác nhau mà thế giới có thể đi đến hồi kết.

Xét một hoán vị \(p_1,p_2,\ldots,p_n\) của các số từ \(1\) đến \(n\). Đặt các số tương ứng lên một vòng tròn theo thứ tự này. Trọng số của cách sắp xếp vòng tròn đó là

trong đó \(p_{n+1}=p_1\).

Hai hoán vị biểu diễn cùng một cách sắp xếp vòng tròn nếu một hoán vị có thể thu được từ hoán vị còn lại bằng cách dịch vòng.

Đảo ngược một cách sắp xếp không làm cho nó trở thành giống nhau; nói cách khác, các cách sắp xếp đối xứng được coi là khác nhau, trừ khi chúng cũng có thể thu được từ nhau bằng một phép dịch vòng.

Hãy tính tổng trọng số của tất cả các cách sắp xếp vòng tròn khác nhau.

Vì đáp án có thể rất lớn, hãy in ra kết quả modulo \(998\,244\,353\).

Input

Mỗi test gồm nhiều test case.

• Dòng đầu tiên chứa số lượng test case \(t\) (\(1 \le t \le 10^4\)).
• Mô tả các test case như sau:
  • Dòng đầu tiên của mỗi test case chứa một số nguyên \(n\) (\(3 \le n \le 2\cdot10^5\)) — số lượng số nguyên được đánh nhãn.
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(0 \le a_i < 998\,244\,353\)).

Đảm bảo rằng tổng \(n\) trên tất cả các test case không vượt quá \(2\cdot10^5\).

Output

Với mỗi test case, in ra một số nguyên — tổng trọng số của tất cả các cách sắp xếp vòng tròn khác nhau, lấy modulo \(998\,244\,353\).

Example

3
3
1 2 3
6
0 1 0 1 0 1
10
114514 1919810 350234 11831 314159265 271828182 123456789 998244352 5201314 23333333

120
12
265885269