P1006：牛客/2025-2/m 又算错了吗？

题目描述

肖恩在自己的数学作业中遇到了这个问题：

在一个二维平面中，边长在 $\{1,2,\ldots,s\}$ 的三角形有多少种不同的形状，且周长不超过 $l$？如果两个三角形可以通过平移和旋转完全重合，则认为它们是相同的形状。注意，不允许翻转。因此，对于 $\triangle ABC$ 和 $\triangle A'B'C'$（$A,B,C$ 和 $A',B',C'$ 按照逆时针顺序排列），如果 $AB=2,BC=3,CA=4$ 且 $A'B'=2,A'C'=4,C'A'=3$，它们不被认为是相同的形状。

肖恩喜欢用二进制来考虑问题，因此他使用数字的二进制表示上面提到的所有数字。他遍历了所有可能的 $(a,b,c)$，试图找到答案，因此他想计算的是满足以下条件的三元组 $(a,b,c)$ 的数量：

• $1\le a,b,c\le s$ 且都是整数；
• $a+b>c,\ a+c>b,\ b+c>a$；
• $a+b+c\le l$。

然后，他从这些三元组中找到对应的不同形状的三角形个数。然而，肖恩数学太烂了，因此当他计算 $a+b+c$ 时，他完全忘记了进位，因此实际上，他得到的是 $a\oplus b\oplus c$ 的结果，即 $a,b,c$ 的按位异或（$XOR$）和。

除了犯了这个错误外，肖恩想知道他是否还犯了其他错误，因此他问你：如果第三个条件是 $a\oplus b\oplus c\le l$ 而不是 $a+b+c\le l$，那么答案是什么。你能帮他吗？

由于答案可能非常大，请输出它关于 $998244353$ 取模的结果。

输入输出格式

输入

每组测试包含多个测试用例。第一行包含测试用例的数量 $t\ (1\le t\le 10^4)$。

每个测试用例由一行组成。该行包含 $2$ 个字符串 $s_l,s_s\ (|s_l|\le 10^5,\ |s_s|\le 10^5)$，表示整数 $l$ 和 $s$ 的二进制表示。保证 $l>0$ 且 $s>0$，并且字符串 $s_l$ 和 $s_s$ 的第一个字符始终为 $1$。

保证单组测试中，$\sum |s_l|\le 5\times 10^5$，$\sum |s_s|\le 5\times 10^5$。

输出

对于每个测试用例，输出 $1$ 个整数——不同形状的三角形数量关于 $998244353$ 取模的结果。

样例

2
101 1111
1111 101

267
25

数据范围

• $1\le t\le 10^4$
• $|s_l|\le 10^5,\ |s_s|\le 10^5$
• $\sum |s_l|\le 5\times 10^5,\ \sum |s_s|\le 5\times 10^5$
• $l>0,\ s>0$