E - Popcount Sum 3

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

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, popcount(y) denotes the number of 1 bits in the binary representation of y. For example, $popcount(5)=2, popcount(16)=1, popcount(25)=3$.

Constraints

$1≤T≤100$ $1≤N<2^{60}$

$1≤K≤60$ $T, N,$ and $K$are integers.

Input

The input is given from Standard Input in the following format:

$T$ $case 1$ $​case 2$ ​⋮ $case T$ $​case i​$ denotes the i-th test case. Each test case is given in the following format: $N$ $K$

Output

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

Sample Input 1

2
20 2
1234567890 17

Sample Output 1

100
382730918

Explantion

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.