9048: GCD Magic

Z is learning GCD theory and he finds a difficult problem:
$$\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(2^i-1,2^j-1)]^K$$
He doesn’t know how to solve it, but he knows it’s easy for you. Please help him. Since the answer can be very large, you only need to print the answer mod 998244353.

The first line contains one integer T (1 ≤ T ≤ 12) which represents the number of test cases. For each test case: One line contains two integers n (1 ≤ n ≤ 109 ) and K (0 ≤ K ≤ 10).

For each test case: Print one line containing one integer which represents the answer