Sum of Cubes of Beautiful Numbers

A positive integer is a beautiful number if its binary representation without leading zeros contains at least 1 and at most 3 zeros. For each closed interval [L,R], find the sum of the cubes of all beautiful integers in it, modulo 998244353. All queries are independent.

输入格式

The first line contains Q, followed by Q lines each with two integers L R. Full original ranges: 1≤Q≤200000, 1≤L≤R≤10^18. Leading zeros are not counted.

输出格式

Output Q integers in input order, one per line, each in 0..998244352. The original text explicitly requires Q results, and the starter's single long return type cannot express multiple queries, so this problem follows the output format in the statement.

样例 1

输入：

2
5 8
10 15

输出：

853
9000

样例 2

输入：

5
1 1
2 2
7 7
8 8
16 16

输出：

0
8
0
512
0

样例 3

输入：

1
1 10

输出：

2654

样例说明

The original first example keeps its input, with the output corrected to 853 and 9000: [5,8] contains 5, 6, 8, and the original explanation missed 6; [10,15] contains 10, 11, 12, 13, 14. The original 153/0 and the explanation's 637/0 both contradict the explicit definition. the single values 1, 2, 7, 8, 16 give 0, 8, 0, 512, 0 respectively; in [1,10], the cubes of 2, 4, 5, 6, 8, 9, 10 sum to 2654.