Editorial: Exceptional Segments

Define prefix XOR:

$$ p_i = 1 \oplus 2 \oplus \cdots \oplus i,\quad p_0=0. $$

For a segment $[l,r]$:

$$ l \oplus (l+1) \oplus \cdots \oplus r = p_r \oplus p_{l-1}. $$

So we need:

$$ p_r = p_{l-1},\quad 1 \le l \le x \le r \le n. $$

Let $a=l-1$ and $b=r$. Then:

$a \in [0, x-1]$
$b \in [x, n]$
and we count pairs $(a,b)$ with $p_a=p_b$.

The well-known formula for prefix XOR is:

$$ p_i = \begin{cases} i, & i \bmod 4 = 0\\ 1, & i \bmod 4 = 1\\ i+1, & i \bmod 4 = 2\\ 0, & i \bmod 4 = 3 \end{cases} $$

From this:

$p_i=0$ appears many times: at $i=0$ and all $i\equiv 3\pmod 4$.
$p_i=1$ appears many times: all $i\equiv 1\pmod 4$.
every other value appears at exactly one index.

Because $[0,x-1]$ and $[x,n]$ are disjoint, values that appear at exactly one index cannot match across the split. Therefore only values 0 and 1 contribute.

If:

$$ z_L=\#\{i\in[0,x-1]:p_i=0\},\quad z_R=\#\{i\in[x,n]:p_i=0\}, $$ $$ o_L=\#\{i\in[0,x-1]:p_i=1\},\quad o_R=\#\{i\in[x,n]:p_i=1\}, $$

then:

$$ \text{answer}=z_L z_R + o_L o_R \pmod{998244353}. $$

Counting residues modulo $4$ in any range is $O(1)$, so each test case is $O(1)$ and total complexity is $O(t)$.