AT_agc075_c [AGC075C] Minimization of Divide

You are given two length- $ N $ sequences of non-negative integers: $ A=(A_1,A_2,\dots,A_N) $ and $ B=(B_1,B_2,\dots,B_N) $ . For a permutation $ P=(P_1,P_2,\dots,P_N) $ of $ (1,2,\dots,N) $ , define the cost of $ P $ as $ \sum_{i=1}^{N} \left \lfloor \frac{A_{P_i}}{2^{B_i}} \right \rfloor $ . Find the number, modulo $ 998244353 $ , of permutations $ P $ that achieve the minimum cost. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ A_1\ A_2\ \dots\ A_N $ $ B_1\ B_2\ \dots\ B_N $

Output $ T $ lines. The $ i $ -th line $ (1 \le i \le T) $ should contain the answer for $ \mathrm{case}_i $ .

### Sample Explanation 1 For the first test case, the cost for each $ P $ is as follows: - For $ P=(1,2) $ , $ \left \lfloor \frac{A_{1}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{2}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{5}{1} \right \rfloor + \left \lfloor \frac{9}{2} \right \rfloor = 9 $ - For $ P=(2,1) $ , $ \left \lfloor \frac{A_{2}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{1}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{9}{1} \right \rfloor + \left \lfloor \frac{5}{2} \right \rfloor = 11 $ Thus, the minimum cost is $ 9 $ , and there is one permutation $ P = (1,2) $ that achieves it. For the second test case, $ P = (1,2,3),(2,1,3) $ achieve the minimum cost of $ 7 $ . For the third test case, $ P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3) $ achieve the minimum cost of $ 6 $ . For the fourth test case, all permutations of $ (1,2,3,4,5) $ achieve the minimum cost of $ 5000000000 $ . ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le A_i \le 10^9 $ - $ 0 \le B_i \le 30 $ - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ .