CF2225D.Exceptional Segments

You are given two integers $ n $ and $ x $ .

Consider the sequence $ [1, 2, 3, \dots, n] $ . You need to find the number of its subsegments that contain $ x $ and have XOR equal to $ 0 $ . In other words, you need to count the number of pairs $ (l, r) $ such that $ 1 \le l \le x \le r \le n $ and $ l \oplus (l+1) \oplus \dots \oplus r = 0 $ , where $ \oplus $ denotes the bitwise exclusive OR.

For example, if $ n = 7 $ and $ x = 6 $ , then the following segments are suitable:

• $ (4, 7) $ , because $ x $ lies in this segment and $ 4 \oplus 5 \oplus 6 \oplus 7 = 0 $ ;
• $ (1, 7) $ , because $ x $ lies in this segment and $ 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus 7 = 0 $ .

Since the answer can be very large, output it modulo $ 998,244,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2 \cdot 10^5 $ ). The description of the test cases follows.

The only line of each test case contains two integers $ n $ and $ x $ ( $ 1 \le x \le n \le 10^{18} $ ).

For each test case, output one integer — the number of suitable segments modulo $ 998,244,353 $ .

null