Cho một xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái latin in hoa. Bạn hãy viết chương trình đếm số xâu \(X\) thỏa đồng thời các điều kiện:

• \(X\) cũng có đúng \(N\) ký tự latin in hoa.
• \(X\) là xâu đối xứng.
• \(rank(X)\le rank(S)\), trong đó \(rank(t)\) thể hiện số lượng xâu chỉ gồm các chữ cái latin in hoa và có thứ tự từ điển nhỏ hơn hẳn xâu \(t\).

Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu chứa số nguyên \(T\) thể hiện số câu hỏi \((T\le 250 \ 000)\).
• Dòng đầu tiên trong \(T\) nhóm dòng tiếp theo chứa một số nguyên \(N\) \(\left(N\le 10^6\right)\), theo sau là một dòng chứa xâu \(S\) chỉ gồm các chữ cái latin in hoa.
• Dữ liệu đảm bảo tổng giá trị \(N\) trong tất cả các câu hỏi không vượt quá \(10^6\).

Output

• In ra \(T\) dòng là câu trả lời cho \(T\) câu hỏi đã cho.

Ví dụ

Sample input 01

3
3
ADA
6
ABCDEF
7
QWERTYX

Sample output 01

4
29
296210