题目描述

题目背景

雾之湖在夏日午后总是格外宁静。冰之妖精琪露诺正努力地想将一整块湖面冻成她心目中的“完美几何图形”——一个标准的正六边形，因为她自认是“最强的”，自然要冻出最强的形状。汗水（或者说冰晶）从她的额角渗出，湖面在她专注的目光下咔嚓咔嚓地凝结。大妖精在一旁，用宽大的叶子为她扇风，并温和地提醒：“琪露诺酱，蕾米莉亚小姐订的红茶时间快到了哦。咲夜小姐说今天有从外界来的新点心呢。”

“马、马上就完成了！”琪露诺头也不回，小脸因为用力而涨红。就在六边形最后一个角即将成型时，一只巨大的红色蝙蝠影子悠然掠过如镜的湖面，翼尖点起一圈漂亮的涟漪。这圈涟漪荡开，轻轻“推”了一下那最后一块冰。“咔嚓”——一声脆响，刚刚还规整的冰晶图案边缘，崩出了一个小小的、滑稽的弧形缺口。

“呜啊——！”琪露诺发出了悲鸣。“帕琪说过，完美的图形是神圣的！这下不完美了！”她气鼓鼓地转身，却发现大妖精正掩嘴轻笑，湖面倒映着红色的洋馆和蓝天白云，那个带缺口的“六边形”冰面，在阳光下闪闪发光，像一枚被咬了一口的、巨大的宝石。远处红魔馆的露台上，仿佛传来银制茶杯轻碰的叮当声。

题目描述

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

其中， \(\texttt{or}\) 表示按位或， \(\texttt{and}\) 表示按位与。

答案对 \(998244353\) 取模。

输入格式

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

接下来是 \(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