F. Binary Function
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$f(x)$$$ be the number of positive integers $$$y$$$ such that $$$y \lt x$$$ and $$$\text{popcount}(y) \gt \text{popcount}(x)$$$, where $$$\text{popcount}(z)$$$ is equal to the number of $$$1$$$s in the binary representation of $$$z$$$.

Given $$$t$$$ testcases of $$$x$$$ in its binary representation, find $$$f(x)$$$ for each test case. Because this number might be too large, output the answer modulo $$$998244353$$$.

Note: $$$|x|$$$ represents the length of $$$x$$$ in its binary representation. Also, some values of $$$x$$$ might be too large to convert to an integer, even with $$$64$$$ bits.

Input

The first line contains $$$t$$$ $$$(1 \leq t \leq 500)$$$, the number of testcases. The description of the test cases follows.

The only line of each test case contains the binary representation of an integer $$$x$$$ $$$(1 \leq |x| \leq 10^6)$$$.

The sum of $$$|x|$$$ across all test cases does not exceed $$$10^6$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy the sum of $$$|x|$$$ across all test cases does not exceed $$$20$$$.

Tests $$$3-6$$$ satisfy the sum of $$$|x|$$$ across all test cases does not exceed $$$5000$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

For each test case, print one integer — $$$f(x)$$$ modulo $$$998244353$$$.

Example
Input
4
1000
11
101011
11001000110
Output
4
0
1
664
Note

In the first test case of the sample, $$$1000$$$ in binary equals 8. $$$f(8) = 4$$$, since $$$3, 5, 6, 7$$$ are less than $$$8$$$, and $$$\text{popcount}(3) = 2, \text{popcount}(5) = 2, \text{popcount}(6) = 2, \text{popcount}(7) = 3$$$ are greater than $$$\text{popcount}(8) = 1$$$.

—

Problem Idea: Mustela_Erminea

Problem Preparation: HaccerKat

Occurrences: Advanced F