In the new semester, TTL and YXH learn two new functions in class: the fifirst function f(x) is defifined as the number of ‘1’ in the binary representation of x, for example, f(1) = 1,f(3) = 2,f(5) = 2; The second function g(x) = f(x & (x >> 1)), where ‘ & ’ denotes bitwise AND, and ‘ >> ’ denotes bitwise right
shift operation.
To test how far they grasp the two functions, their teacher assigns a class exercise. In this exercise, an integer k is given, then both TTL and YXH need to choose an interval respectively, denoted as [l1, r1] and [l2, r2]. After that, the teacher asks them to fifind all pairs (x, y) such that x ∈ [l1, r1], y ∈ [l2, r2], and x ⊕ y ≤ k, then calculate the sum of g(x|y)! , where ‘ ⊕ ’ denotes bitwise XOR, ‘ | ’ denotes bitwise OR, and ‘ ! ’ is the factorial notation. If there is no such pair, the answer is 0.
TTL and YXH think the problem is too difficult, so they ask smart you for help. Given the integer k and the two intervals [l1, r1] and [l2, r2], can you help them fifigure out the answer?
Since the answer is likely to be very large, you just have to fifigure out the answer modulo 998244353.
输入描述:
The fifirst line contains an integer T(1 ≤ T ≤ 103 ), denoting the number of test cases.
The only line of each test case contains fifive integers l1, r1, l2, r2, k (1 ≤ l1 ≤ r1 ≤ 109 , 1 ≤ l2 ≤ r2 ≤ 109 , 0 ≤ k ≤ 109 ) separated by space.
输出描述:
For each test case, output one line with an integer, indicating the answer modulo 998244353.
示例1
输入
复制
3
1 3 1 3 2
2 2 3 3 0
1 14 5 14 114514
说明
For the fifirst test case, there are 7 possible pairs:
(1, 1),(1, 3),(2, 2),(2, 3),(3, 1),(3, 2),(3, 3).
So the answer is: 0! + 1! + 0! + 1! + 1! + 1! + 1! = 7.
For the second test case, there isn’t any possible pair, so the answer is 0.