AT_abc406_e [ABC406E] Popcount Sum 3

You are given positive integers $ N $ and $ K $ . Find the **sum**, modulo $ 998244353 $ , of all positive integers $ x $ that do not exceed $ N $ and satisfy the following condition: - the popcount of $ x $ is exactly $ K $ . You are given $ T $ test cases; solve each of them. What is popcount? For a positive integer $ y $ , $ \mathrm{popcount}(y) $ denotes the number of $ 1 $ bits in the binary representation of $ y $ . For example, $ \mathrm{popcount}(5)=2 $ , $ \mathrm{popcount}(16)=1 $ , $ \mathrm{popcount}(25)=3 $ .

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ denotes the $ i $ -th test case. Each test case is given in the following format: > $ N $ $ K $

Output $ T $ lines. The $ i $ -th line $ (1 \leq i \leq T) $ should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, there are nine positive integers not exceeding $ 20 $ whose popcount is $ 2 $ : $ 3, 5, 6, 9, 10, 12, 17, 18, 20 $ . Their sum is $ 100 $ . The remainder when $ 100 $ is divided by $ 998244353 $ is $ 100 $ , so output `100` on the first line. Remember to output the sum modulo $ 998244353 $ . ### Constraints - $ 1 \leq T \leq 100 $ - $ 1 \leq N < 2^{60} $ - $ 1 \leq K \leq 60 $ - $ T $ , $ N $ , and $ K $ are integers.