9617: Miscalculated Triangles

In his homework, Sean ran into this problem:

--- How many different shapes of triangles are there in a 2D-plane, with lengths of its sides in $\{1,2,\dots ,s\}$ and perimeter no longer than $l$ ? Two triangles are considered to be in the same shape if they can completely overlap using only translation and rotation. Note that flips are not allowed. So for ΔABC and ΔA′B′C′ (A,B,C and A′,B′,C′ are listed anti-clockwise.), if AB=2,BC=3,CA=4 and A′B′=2,A′C′=4,C′A′=3, they are not considered to be in the same shape.

• $1\le a,b,c\le s$ and are all integers.
• $a+b>c,a+c>b,b+c>a$
• $a+b+c\le l$

Then, he chose from these triplets such that each triplet chosen represents a different triangle. However, Sean was so bad at math that when he calculated $a+b+c$ , he totally forgot about the carries, and therefore got the result of $a\oplus b\oplus c$, which is the bitwise exclusive OR (XOR) sum of $a,b$ and $c$ .

Despite this mistake, Sean wants to know if he makes other mistakes, so he asks you about the answer if the third condition is $a\oplus b\oplus c\le l$ rather than $a+b+c\le l$. Can you help him out with this?

Since the answer can be enormous, output it modulo $998244353$ .

Each test contains multiple test cases. The first line contains the number of test cases T (1≤T≤10⁴) .
Each test case consists of a single line. The line contains $2$ strings sl,ss (∣sl∣≤10⁵,∣ss∣≤10⁵) , the binary representation of the integers $l$ and $s$ . It is guaranteed that l>0 and $s>0$, and the first character of string s_s and s_l is always $1$ .
It is guaranteed that ∑∣s_l∣ over all test cases in one test will not exceed 5×10⁵ and ∑∣ss∣ over all test cases in one test will not exceed 5×10⁵.

For each test case, output $1$ integer: the number of triangles in different shapes modulo $998244353$ .