题目描述

给定两个整数 $n$ 和 $x$。

有自然数序列 $[1,2,3,\dots,n]$，请你统计满足以下两个条件的子区间数量：

1. 区间包含位置 $x$；
2. 区间内所有数的按位异或和等于 $0$。

形式化地说：统计满足 $1 \le l \le x \le r \le n$ 且 $l \oplus (l+1) \oplus \dots \oplus r = 0$ 的数对 $(l,r)$ 的个数，其中 $\oplus$ 表示按位异或运算。

例如：当 $n=7$，$x=6$ 时，合法区间有：

• $(4,7)$：包含 $x$，且 $4 \oplus 5 \oplus 6 \oplus 7 = 0$；
• $(1,7)$：包含 $x$，且 $1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus 7 = 0$。

答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

多组测试数据。 第一行一个整数 $t$（$1 \le t \le 2\cdot 10^5$），表示测试数据组数。

每组测试数据一行，包含两个整数 $n,x$（$1 \le x \le n \le 10^{18}$）。

输出格式

对每组测试数据，输出一行一个整数，表示合法区间数量对 $998244353$ 取模后的值。

5
5 5
8 1
15 8
10 10
5989566119 1996588700

1
2
10
0
99996

来源

https://codeforces.com/contest/2225/problem/D