원형으로 배열된 이진 문자열 $a_0a_1a_2 \dots a_{n-1}$이 주어집니다. 매초마다 모든 $01$을 동시에 $10$으로 바꿉니다. 즉, $a_i = 0$이고 $a_{(i+1) \bmod n} = 1$이면, $a_i$와 $a_{(i+1) \bmod n}$을 서로 바꿉니다. 예를 들어, $100101110$은 $001010111$로 바뀝니다.

무한한 시간 동안 나타날 수 있는 서로 다른 문자열의 개수를 $998244353$으로 나눈 나머지를 구해야 합니다.

참고: 두 문자열 $a_0a_1 \dots a_{n-1}$과 $b_0b_1 \dots b_{n-1}$은 $a_i \neq b_i$를 만족하는 정수 $i \in \{0, 1, \dots, n-1\}$가 존재하면 서로 다른 것으로 간주합니다. 따라서 문자열의 순환 시프트는 원래 문자열과 다를 수 있습니다.

입력

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^6$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 이진 문자열 $a_0a_1 \dots a_{n-1}$ ($a_i \in \{0, 1\}$)이 주어집니다.

모든 테스트 케이스에 대한 문자열 길이의 합은 $10^7$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 문제의 정답을 한 줄에 하나씩 출력합니다.

예제

입력 1

3
1
001001
0001111

출력 1

1
3
9