Bạn được cho một xâu nhị phân $a_0a_1a_2 \dots a_{n-1}$ được sắp xếp trên một vòng tròn. Mỗi giây, bạn sẽ thay đổi đồng thời mọi $01$ thành $10$. Nói cách khác, nếu $a_i = 0$ và $a_{(i+1) \pmod n} = 1$, bạn sẽ hoán đổi $a_i$ và $a_{(i+1) \pmod n}$. Ví dụ, chúng ta sẽ biến đổi $100101110$ thành $001010111$.

Bạn cần trả lời có bao nhiêu xâu khác nhau sẽ xuất hiện trong vô hạn giây, theo modulo $998244353$.

Lưu ý: Hai xâu $a_0a_1 \dots a_{n-1}$ và $b_0b_1 \dots b_{n-1}$ được coi là khác nhau nếu tồn tại một số nguyên $i \in \{0, 1, \dots, n-1\}$ sao cho $a_i \neq b_i$. Do đó, các phép dịch vòng của một xâu có thể khác với xâu ban đầu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^6$) – số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa một xâu nhị phân $a_0a_1 \dots a_{n-1}$ ($a_i \in \{0, 1\}$).

Đảm bảo rằng tổng độ dài của các xâu qua tất cả các bộ test không vượt quá $10^7$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất đại diện cho kết quả trên một dòng.

Ví dụ

Dữ liệu vào 1

3
1
001001
0001111

Dữ liệu ra 1

1
3
9