题目描述

以二进制形式给出两个非负整数 $s$ 和 $t$，请求出方程 $a \times b=(a$ or $b) \times (a$ and $b)$ 在 $a$ 和 $b$ 都取 $[s,t]$ 中的整数时，共有几组解。

其中，or 表示按位或，and 表示按位与。

答案对 $998244353$ 取模。

输入格式

输入的第一行包含一个整数 $Q(1\le Q \le20)$，表示测试用例的数量。

接下来是 $Q$ 个测试用例的描述。

每个测试用例，共一行，包含两个 01 字符串 $S$ 和 $T$（字符串 $S$ 和 $T$ 的长度 $|S|$ 和 $|T|$ 有 $1 \le |S|,|T| \le 5 \times 10^5$，分别表示 $s$ 和 $t$ 的二进制形式。保证给定的 $s$ 和 $t$ 的二进制形式无前导零，且 $s \le t$。

输出格式

对于每个测试用例，输出一行，包含一个非负整数，表示答案对 $998244353$ 取模的值。

样例

6
11 1000
1000 1001
0 100
11 111
10 111
0 11111

18
4
17
17
24
454