CF2075E XOR Matrix

For two arrays $ a = [a_1, a_2, \dots, a_n] $ and $ b = [b_1, b_2, \dots, b_m] $ , we define the XOR matrix $ X $ of size $ n \times m $ , where for each pair $ (i,j) $ ( $ 1 \le i \le n $ ; $ 1 \le j \le m $ ) it holds that $ X_{i,j} = a_i \oplus b_j $ . The symbol $ \oplus $ denotes the bitwise XOR operation. You are given four integers $ n, m, A, B $ . Count the number of such pairs of arrays $ (a, b) $ such that: - $ a $ consists of $ n $ integers, each of which is from $ 0 $ to $ A $ ; - $ b $ consists of $ m $ integers, each of which is from $ 0 $ to $ B $ ; - in the XOR matrix formed from these arrays, there are no more than two distinct values.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of one line containing four integers $ n, m, A, B $ ( $ 2 \le n, m, A, B \le 2^{29} - 1 $ ).

For each test case, output one integer — the number of pairs of arrays $ (a, b) $ that satisfy all three conditions. Since this number can be very large, output it modulo $ 998244353 $ .