Nhân dịp lễ giáng sinh năm 2012, Thức được anh trai Kiên tặng cho ~T~ món quà, mỗi món quà chứa ~n~ lá bài và các con số, lá bài thứ ~i~ sẽ được ghi số ~a_i~ ở trên mặt lá bài.

Sau khi đặt ~n~ là bài lên trên bàn, Thức nhận ra các con số ghi trên các lá bài có thể ghép thành những số lớn hơn. Ví dụ Thức có các lá bài với các số là ~1~, ~31~ và ~12~, Thức có thể đặt chúng lên bàn và nhận được số ~13112~.

Thấy Thức đang xếp các lá bài nên Kiên đã hỏi Thức xem có bao nhiêu cách xếp các lá bài như thế. Với trí thông minh của mình, dù chỉ 11 tuổi nhưng Thức biết được có tất cả ~n!~ cách để đặt ~n~ là bài lên bàn rồi ghép chúng lại.

Tuy có nhiều cách xếp nhưng Thức chỉ thích những cách xếp mà con số nhận được là bội của ~11~. Chẳng hạn cách xếp 3 lá bài ~1~, ~31~ và ~12~ đã được đề cập trên kia chính là một cách xếp thoả mãn vì ~13112 = 1192 \times 11~ nhưng nếu ta xếp thành ~31112~ thì số nhận được sẽ không là bội của ~11~.

Tới đây thì Thức băn khoăn không biết trong ~n!~ cách xếp thì có bao nhiêu cách xếp ~n~ là bài để số nhận được là một bội của ~11~.

Suy nghĩ một hồi lâu Thức vẫn không tìm được đáp án, thấy vậy Kiên đã dạy cho Thức cách xác định một số có chia hết cho ~11~ hay không: ta lấy tổng các chữ số ở hàng lẻ trừ đi tổng các chữ số ở hàng chẵn, nếu kết quả này chia hết cho ~11~ thì số đó chia hết cho ~11~. Ví dụ số ~13112~ có các tổng các chữ số ở hàng lẻ là ~1 + 1 + 2 = 4~, tổng các chữ số ở hàng chẵn là ~3 + 1 = 4~, do ~4 - 4 = 0~ chia hết cho ~11~ nên ~13112~ chia hết cho ~11~. Với số ~31112~, do ~(3 + 1 + 2) - (1 + 1) = 4~ không chia hết cho ~11~ nên số này không là bội của ~11~.

Tuy biết được dấu hiệu chia hết cho ~11~ nhưng Thức vẫn chưa thể tìm được đáp án, là một thí sinh của VNOI Online 2021, bạn có thể giúp Thức tìm đáp án cho bài toán này được không?

Input

Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10)~ chính là số lượng món quà mà Kiên tặng cho Thức.

Tiếp theo gồm có ~T~ nhóm dòng biểu diễn các món quà, mỗi nhóm dòng sẽ có dạng sau đây:

• Dòng đầu tiên sẽ chứa số nguyên dương ~n~ là số lượng lá bài của món quà này.
• Dòng tiêp theo chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~ là số được ghi lên các lá bài.

Output

Với mỗi món quà, in ra số lượng cách xếp để nhận được một số mà Thức yêu thích trên một dòng, do kết quả rất lớn nên chỉ cần in ra kết quả trong modulo ~998244353~.

Giới hạn

Gọi ~S~ là tổng ~n~ của mọi test trong một input. Trong mọi input ta có ~1 \le S \le 2000~.

• ~10~% số điểm có ~1 \le S \le 8~
• ~10~% số điểm tiếp theo, mọi số ghi trên lá bài đều là số có chẵn chữ số.
• ~30~% số điểm tiếp theo, mọi số ghi trên lá bài đều là số có lẻ chữ số.
• ~50~% số điểm còn lại không có giới hạn gì thêm.

Sample Input

4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9

Sample Output

2
2
2
31680

Note

Lưu ý rằng với Thức thì mọi lá bài là khác nhau, kể cả khi các con số được ghi trên lá bài là giống nhau. Chẳng hạn nếu có 2 lá bài đều được viết số ~1~ thì kết quả sẽ là ~2~.