Given two positive integers N and M, let S denote the set of all the arrays of size N such that each element of the array lies in the range [1, M]. Since there are M^{N} such arrays, the size of S is M^{N}.

Let X_{i} denote the [bitwise AND] of all elements of the i^{th} array in the set, where 1 ≤ i ≤ M^{N}.  
Find the value \sum_{i = 1}^{M^{N}} X_{i}. Since the answer can be huge, output the answer modulo 998244353.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two integers N and M, the size of the array, and the maximum limit of elements.

------ Output Format ------ 

For each test case, print the value \sum_{i = 1}^{M^{N}} X_{i}. Since the answer can be huge, output the answer modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2\cdot10^{5}$
$1 ≤ M ≤ 10^{9}$

----- Sample Input 1 ------ 
2
2 2
2 3

----- Sample Output 1 ------ 
3
12
----- explanation 1 ------ 
Test case $1$: The set $S$ contains $\{[1,1], [1,2], [2,1], [2,2]\}$. The array $X = [1\& 1, 1\& 2, 2\& 1, 2\& 2] = [1, 0, 0, 2]$. Thus, sum of all elements of $X$ is $1+0+0+2 = 3$.

Test case $2$: The set $S$ contains $\{[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]\}$. The array $X = [1\& 1, 1\& 2, 1\& 3, 2\& 1, 2\& 2, 2\& 3, 3\& 1, 3\& 2, 3\& 3] = [1, 0, 1, 0, 2, 2, 1, 2, 3]$. Thus, sum of all elements of $X$ is $12$.

Difficulty: HARD
Tags: Bit manipulation

Combinatorics

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
mod = 998244353

def counts(m, i):
	count = m >> i + 1 << i
	if m >> i & 1:
		count += m & (1 << i) - 1
	return count

def solve(n, m):
	ans = 0
	for i in range(32):
		count = counts(m + 1, i)
		if count:
			ans = (ans + pow(count, n, mod) * pow(2, i, mod) % mod) % mod
		else:
			break
	return ans
for _ in range(int(input())):
	print(solve(*map(int, input().split())))


t = int(input())
mod = 998244353
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	for bit in range(31):
		k = m // (2 << bit) * (1 << bit) + max(0, m % (2 << bit) - (1 << bit) + 1)
		ct = pow(k, n, mod)
		ans = (ans + ct * (1 << bit)) % mod
	print(ans)


mod = 998244353

def arrctr(n, m):
	ans = 0
	for bit in range(30):
		ct = m // (2 << bit) * (1 << bit)
		ct += max(0, m % (2 << bit) - (1 << bit) + 1)
		ans += pow(ct, n, mod) << bit
	return ans % mod
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(arrctr(n, m))


def solve(n, m):
	m += 1
	ans = 0
	mod = 998244353
	for bit in range(30):
		cnt = m // (2 << bit)
		cnt = cnt * (1 << bit)
		cnt += max(0, m % (2 << bit) - (1 << bit))
		ans += pow(cnt, n, mod) * (1 << bit)
	print(ans % mod)
testCase = int(input())
for _ in range(testCase):
	(n, limit) = map(int, input().split())
	solve(n, limit)


t = int(input())
mod = 998244353
for i in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	for j in range(50):
		k = m // (2 << j) * (1 << j) + max(0, m % (2 << j) - (1 << j) + 1)
		ct = pow(k, n, mod)
		ans = (ans + ct * (1 << j)) % mod
	print(ans)


mod = 998244353
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for bit in range(30):
		ct = m // (2 << bit) * (1 << bit)
		ct += max(0, m % (2 << bit) - (1 << bit) + 1)
		ans += pow(ct, n, mod) << bit
	print(ans % mod)


def councoun(iikm, jjkm):
	return (iikm // (1 << jjkm + 1) << jjkm) + max(0, iikm % (1 << jjkm + 1) - (1 << jjkm) + 1)

def powepowe(bbkm, nnkm):
	s = 1
	while nnkm:
		if nnkm % 2 == 1:
			s = s * bbkm % 998244353
		bbkm = bbkm * bbkm % 998244353
		nnkm = nnkm // 2
	return s
for t in range(int(input())):
	(nnkm, mmkm) = map(int, input().split())
	s = 0
	for jjkm in range(31):
		s = (s + (powepowe(councoun(mmkm, jjkm), nnkm) << jjkm) % 998244353) % 998244353
	print(s)


MOD = 998244353
for _ in range(int(input())):
	(n, m) = [int(s) for s in input().split()]
	m += 1
	ans = 0
	cur = 1
	while cur <= m:
		cur = cur << 1
		w = m // cur * (cur // 2) + max(0, m % cur - cur // 2)
		ans = (ans + cur // 2 * pow(w, n, MOD) % MOD) % MOD
	print(ans)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
mod = 998244353
for _ in range(ni()):
	(n, m) = mi()
	res = 0
	for bit in range(31):
		b2 = 2 << bit
		count = m // b2 * (b2 >> 1) + max(0, m % b2 - (b2 >> 1) + 1)
		res += pow(count, n, mod) << bit
	print(res % mod)


mod = 998244353
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	mult = 1
	for k in range(31):
		block = m // (2 * mult)
		cnt = block * mult
		cnt += max(0, m % (2 * mult) - mult + 1)
		ans += pow(cnt, n, mod) * mult
		ans %= mod
		mult *= 2
	print(ans)


mod = 998244353
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	res = 0
	for bit in range(31):
		b2 = 2 << bit
		count = m // b2 * (b2 >> 1) + max(0, m % b2 - (b2 >> 1) + 1)
		res += pow(count, n, mod) << bit
	print(res % mod)


import math
from functools import reduce
import sys
sys.setrecursionlimit(1000000)

def read(func=str, sep=None):
	return list(map(func, input().split(sep)))

def read_ints(sep=None):
	return read(func=int, sep=sep)

def read_int():
	return int(input())

def print_array(arr, sep=' '):
	print(sep.join(map(str, arr)))

def bitcount(num):
	bits = 0
	while num:
		if num & 1:
			bits += 1
		num >>= 1
	return bits

def highest_bit(n):
	count = 0
	while n != 0:
		count += 1
		n >>= 1
	return count - 1

def modpow(num, pow, mod):
	if pow == 0:
		return 1
	c = modpow(num, pow // 2, mod)
	if pow & 1:
		return c ** 2 % mod * num % mod
	else:
		return c ** 2 % mod
test_cases = read_int()
mod = 998244353
for _ in range(test_cases):

	def has_bit_set(num, bit):
		high = highest_bit(num)
		if high < bit:
			return 0
		if high == bit:
			return num - 2 ** high + 1
		return (1 << high - 1) + has_bit_set(num - (1 << high), bit)

	def get_count(num, room, index):
		return modpow(has_bit_set(num, index), room, mod)
	(n, m) = read_ints()
	sum = 0
	for i in range(highest_bit(m) + 1):
		sum += get_count(m, n, i) * (1 << i)
		sum %= mod
	print(sum)


import time
import sys
import math

def get_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
input = sys.stdin.readline
(mod, infi) = (998244353, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from heapq import heappop, heappush, heapify
from itertools import accumulate, combinations, combinations_with_replacement, permutations
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
normal = lambda : input().split()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)

def solve(n, m):
	res = 0
	for bit in range(30):
		lc = m // (2 << bit) * (1 << bit)
		lc += max(0, m % (2 << bit) - (1 << bit) + 1)
		res += pow(lc, n, mod) << bit
	return res % mod
T = inty()
for _ in range(T):
	(n, m) = mappy()
	print(solve(n, m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sums = 0
	for i in range(31):
		sums += pow((m // (1 << i + 1) << i) + max(0, m % (1 << i + 1) - (1 << i) + 1), n, 998244353) << i
	print(sums % 998244353)


P = 998244353

def max_set_bit(n: int):
	k = 0
	while n:
		n >>= 1
		k += 1
	return k - 1

def numbers_with_kth_bit_set(M: int, k: int):
	M += 1
	b = 1 << k
	n = M // b
	return n // 2 * b + M % b * (n % 2)

def mod_pow(b, e, p):
	ans = 1
	while e > 0:
		if e % 2:
			ans = ans * b % p
		e //= 2
		b = b * b
	return ans

def mod_pow(b, e, p):
	if e == 0:
		return 1
	ans = mod_pow(b, e // 2, p)
	ans = ans * ans % p
	if e % 2:
		ans = ans * b % p
	return ans
t = int(input())
for _ in range(t):
	(N, M) = list(map(int, input().split()))
	answer = 0
	base = 1
	for k in range(31):
		m = numbers_with_kth_bit_set(M, k)
		counts = mod_pow(m, N, P)
		answer = (answer + base * counts) % P
		base = base * 2 % P
		k += 1
		if m == 0:
			break
	print(answer)


MOD = 998244353

def power(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % MOD
		b = b * b % MOD
		n //= 2
	return s

def count(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	for i in range(31):
		s = (s + (power(count(m, i), n) << i) % MOD) % MOD
	print(s)


from math import log2
p = 998244353

def razn(x, y):
	return (x - y) % p

def slog(x, y):
	return (x + y) % p

def mult(x, y):
	return x * y % p

def pow(x, y):
	s = x
	res = 1
	while y > 0:
		a = y % 2
		if a:
			res = mult(res, s)
		s = mult(s, s)
		y = y // 2
	return res

def delen(x, y):
	return mult(x, pow(y, p - 2))
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	q = int(log2(m)) + 1
	W = [0] * q
	m1 = m
	s = []
	while m1 > 0:
		s.append(m1 % 2)
		m1 = m1 // 2
	for x in range(len(s)):
		W[x] = s[x]
	s.reverse()
	zap = []
	for x in range(len(s)):
		if s[x]:
			for y in range(len(s) - 1 - x):
				W[y] += 2 ** (len(s) - x - 2)
			for y in zap:
				W[y] += 2 ** (len(s) - x - 1)
			zap.append(len(s) - 1 - x)
	res = 0
	e = 1
	for x in range(q):
		u = W[x]
		res = slog(res, mult(pow(W[x], n), e))
		e = mult(e, 2)
	print(res)


mod = 998244353

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y //= 2
		x = x * x % p
	return res

def power_ka_function(a, b):
	return a // 2 ** (b + 1) * 2 ** b

def rem_ka_function(a, b):
	res = a % 2 ** (b + 1) - 2 ** b + 1
	if res < 0:
		return 0
	return res

def solve():
	(size, limit) = map(int, input().split())
	ans = 0
	for i in range(32):
		var = power_ka_function(limit, i) + rem_ka_function(limit, i)
		var = power(var, size, mod)
		var %= mod
		var *= 2 ** i
		ans += var
		ans %= mod
	print(ans % mod)
t = int(input())
for _ in range(t):
	solve()


def Sets(n: int, m: int):
	if m == 1:
		return [[n]]
	ans = []
	for i in range(n + 1):
		ans += [[i] + e for e in Sets(n - i, m - 1)]
	return ans

def lpow(e: int, i: int):
	if i == 0:
		return 2 ** 31 - 1
	return e

def relu(x):
	return max(0, x)

def nCr2(n: int, r: int):
	ans = 1
	for i in range(r):
		ans *= n - i
		ans //= i + 1
	return ans

def nCr(n: int, r: list):
	ans = 1
	for i in range(len(r)):
		ans *= nCr2(n, r[i])
		n -= r[i]
	return ans

def fc(a, b):
	t1 = a % (1 << b + 1) - (1 << b) + 1
	t2 = a // (1 << b + 1)
	ret = relu(t1) + (t2 << b)
	return ret

def binpow(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % 998244353
		a = a * a % 998244353
		b >>= 1
	return res

def f(n: int, m):
	ans = 0
	for e in Sets(n, m):
		term = 2 ** 31 - 1
		p = 1
		for i in e:
			term &= lpow(p, i)
			p += 1
		ans += term * nCr(n, e) % 998244353
	return ans % 998244353

def f2(n, m):
	ans = 0
	for i in range(20 + 11):
		ans += binpow(fc(m, i), n) << i
	return ans % 998244353
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(f2(n, m))


for _ in range(int(input())):
	(x, y) = map(int, input().split())

	def solve(arr, n):
		c = 1
		while n:
			if n % 2 == 1:
				c *= arr % 998244353
			arr = arr * arr % 998244353
			n = n // 2
		return c

	def solve1(m, l):
		return (m // (1 << l + 1) << l) + max(0, m % (1 << l + 1) - (1 << l) + 1)

	def result():
		ans = 0
		for j in range(31):
			ans = (ans + (solve(solve1(y, j), x) << j) % 998244353) % 998244353
		return ans
	print(result())


def councoun(iik, jjk):
	return (iik // (1 << jjk + 1) << jjk) + max(0, iik % (1 << jjk + 1) - (1 << jjk) + 1)

def powepowe(bbk, nnk):
	s = 1
	while nnk:
		if nnk % 2 == 1:
			s = s * bbk % 998244353
		bbk = bbk * bbk % 998244353
		nnk = nnk // 2
	return s
t = int(input())
for h in range(t):
	(nnk, mmk) = map(int, input().split())
	s = 0
	for jjk in range(31):
		s = (s + (powepowe(councoun(mmk, jjk), nnk) << jjk) % 998244353) % 998244353
	print(s)


from math import log2
mod = 998244353
po2 = [pow(2, i) for i in range(32)]

def solve(n, m):
	s = 0
	for i in range(int(log2(m)) + 1):
		k = m - m % po2[i + 1]
		t = k // 2 + max(0, m - k - po2[i] + 1)
		if not t:
			break
		s += pow(t, n, mod) * po2[i] % mod
		s %= mod
	return s
for _ in range(int(input())):
	(a, b) = map(int, input().strip().split())
	print(solve(a, b))


MOD = 998244353

def calculatePower(i, j):
	sums = 1
	while j:
		if j % 2 == 1:
			sums = sums * i % MOD
		i = i * i % MOD
		j //= 2
	return sums

def countCheck(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	sums = 0
	for i in range(31):
		sums = (sums + (calculatePower(countCheck(M, i), N) << i) % MOD) % MOD
	print(sums)


def councoun(iiii, jjjj):
	return (iiii // (1 << jjjj + 1) << jjjj) + max(0, iiii % (1 << jjjj + 1) - (1 << jjjj) + 1)

def powepowe(bbbb, nnnn):
	s = 1
	while nnnn:
		if nnnn % 2 == 1:
			s = s * bbbb % 998244353
		bbbb = bbbb * bbbb % 998244353
		nnnn = nnnn // 2
	return s
t = int(input())
for h in range(t):
	(nnnn, mmmm) = map(int, input().split())
	s = 0
	for jjjj in range(31):
		s = (s + (powepowe(councoun(mmmm, jjjj), nnnn) << jjjj) % 998244353) % 998244353
	print(s)


def councoun(iii, jjj):
	return (iii // (1 << jjj + 1) << jjj) + max(0, iii % (1 << jjj + 1) - (1 << jjj) + 1)

def powepowe(bbb, nnn):
	s = 1
	while nnn:
		if nnn % 2 == 1:
			s = s * bbb % 998244353
		bbb = bbb * bbb % 998244353
		nnn = nnn // 2
	return s
t = int(input())
for h in range(t):
	(nnn, mmm) = map(int, input().split())
	s = 0
	for jjj in range(31):
		s = (s + (powepowe(councoun(mmm, jjj), nnn) << jjj) % 998244353) % 998244353
	print(s)


def fast_mod_exp(n, exp, mod):
	if exp == 0:
		return 1 % mod
	b = binary(exp, 0)
	res = 1
	current = n
	for i in range(len(b)):
		if b[len(b) - i - 1] == 1:
			res *= current
			res %= mod
		current *= current
		current %= mod
	return res

def binary(n, min_size):
	if n == 0:
		return [0]
	res = []
	while n > 0 or len(res) < min_size:
		res.append(n % 2)
		n //= 2
	return list(reversed(res))

def get_count(p, limit, mod):
	bl = binary(limit, 32)
	res = 0
	e = 1
	for (i, el) in enumerate(bl):
		current_p = len(bl) - i - 1
		if p == current_p:
			if el == 0:
				break
			else:
				e = 0
				continue
		if len(bl) - i - (1 + e) < 0:
			break
		if el == 0:
			continue
		res += 2 ** (len(bl) - i - (1 + e))
		res %= mod
	return res

def f(n, limit, mod):
	res = 0
	p = 0
	while 2 ** p <= limit:
		count = get_count(p, limit, mod)
		count = fast_mod_exp(count, n, mod)
		res += count * 2 ** p
		res %= mod
		p += 1
	return res
t = int(input())
for i in range(t):
	(n, m) = [int(el) for el in input().split(' ')]
	print(f(n, m + 1, 998244353))


def councoun(ii, jj):
	return (ii // (1 << jj + 1) << jj) + max(0, ii % (1 << jj + 1) - (1 << jj) + 1)

def powepowe(bb, nn):
	s = 1
	while nn:
		if nn % 2 == 1:
			s = s * bb % 998244353
		bb = bb * bb % 998244353
		nn = nn // 2
	return s
t = int(input())
for h in range(t):
	(nn, mm) = map(int, input().split())
	s = 0
	for jj in range(31):
		s = (s + (powepowe(councoun(mm, jj), nn) << jj) % 998244353) % 998244353
	print(s)


for _1 in range(int(input())):
	(n, m) = map(int, input().split())

	def ans(a, b):
		return (a // (1 << b + 1) << b) + max(0, a % (1 << b + 1) - (1 << b) + 1)

	def list1(c, d):
		cou = 1
		while d:
			if d % 2 == 1:
				cou = cou * c % 998244353
			c = c * c % 998244353
			d = d // 2
		return cou
	v = 0
	for l in range(31):
		v = (v + (list1(ans(m, l), n) << l) % 998244353) % 998244353
	print(v)


def conu(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)

def pwoe(a, b):
	s = 1
	while b:
		if b % 2 == 1:
			s = s * a % 998244353
		a = a * a % 998244353
		b = b // 2
	return s
c = int(input())
for h in range(c):
	(y, u) = map(int, input().split())
	s = 0
	for j in range(31):
		s = (s + (pwoe(conu(u, j), y) << j) % 998244353) % 998244353
	print(s)


def get_possibilities(M):
	result = [0] * M.bit_length()
	bits = [b for b in f'{M:b}']
	for (i, b) in enumerate(bits):
		if b == '1':
			result[i] += 1
			if i == M.bit_length():
				break
			factor = 1 << M.bit_length() - i - 1
			resid = M % factor
			result[i] += resid
			for j in range(i + 1, len(result)):
				result[j] += factor // 2
	return result[::-1]
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	possibilities = get_possibilities(M)
	result = 0
	modulo = 998244353
	for (i, p) in enumerate(possibilities):
		result += pow(2, i, modulo) * pow(p, N, modulo)
		result %= modulo
	print(result)


def coun(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)

def powe(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % 998244353
		b = b * b % 998244353
		n = n // 2
	return s
t = int(input())
for h in range(t):
	(n, m) = map(int, input().split())
	s = 0
	for j in range(31):
		s = (s + (powe(coun(m, j), n) << j) % 998244353) % 998244353
	print(s)


for i in range(int(input())):
	(n, m) = map(int, input().split())

	def array(a, n):
		c = 1
		while n:
			if n % 2 == 1:
				c = c * a % 998244353
			a = a * a % 998244353
			n = n // 2
		return c

	def sol(q, w):
		return (q // (1 << w + 1) << w) + max(0, q % (1 << w + 1) - (1 << w) + 1)

	def res():
		v = 0
		for j in range(31):
			v = (v + (array(sol(m, j), n) << j) % 998244353) % 998244353
		return v
	print(res())


import io, os, sys

def print(*args, sep=' ', end='\n'):
	string = sep.join(map(str, args)) + end
	sys.stdout.write(string)

def debug(*args, sep=' ', end='\n'):
	string = 'Debug: ' + sep.join(map(str, args)) + end
	sys.stderr.write(string)
MOD = 998244353

def pos(M, i):
	sub = 1 << i
	if M < sub:
		return 0
	if M & sub:
		smol = 1 + (M & sub - 1)
	else:
		smol = 0
	parts = M >> i + 1
	result = parts * sub + smol
	return result % MOD

def solve(N, M):
	total = 0
	for i in range(30):
		res = (1 << i) % MOD
		total += res * pow(pos(M, i), N, MOD)
		total %= MOD
	return total
T = int(input())
for case in range(1, T + 1):
	(N, M) = map(int, input().split())
	print(solve(N, M))


def increase(a, t):
	r = 1
	while t:
		if t % 2 == 1:
			r = r * a % 998244353
		a = a * a % 998244353
		t //= 2
	return r

def counter(i, j):
	res = (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	for i in range(0, 31, 1):
		s = (s + (increase(counter(m, i), n) << i) % 998244353) % 998244353
	print(s)


def power(c, n):
	sums = 1
	while n > 0:
		if n % 2 == 1:
			sums *= c % 998244353
		c *= c % 998244353
		n //= 2
	return sums

def c(m, i):
	return (m // (1 << i + 1) << i) + max(0, m % (1 << i + 1) - (1 << i) + 1)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sums = 0
	for i in range(31):
		sums += (power(c(m, i), n) << i) % 998244353
	print(sums % 998244353)


def p(a, nu):
	c = 1
	while nu:
		if nu % 2 == 1:
			c = c * a % 998244353
		a = a * a % 998244353
		nu //= 2
	return c

def c(ar1, ar2):
	return (ar1 // (1 << ar2 + 1) << ar2) + max(0, ar1 % (1 << ar2 + 1) - (1 << ar2) + 1)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	for i in range(0, 31):
		s = (s + (p(c(m, i), n) << i) % 998244353) % 998244353
	print(s)


def pow(bg, num):
	count = 1
	while num:
		if num % 2 == 1:
			count = count * bg % 998244353
		bg = bg * bg % 998244353
		num //= 2
	return count

def coun(arg1, arg2):
	return (arg1 // (1 << arg2 + 1) << arg2) + max(0, arg1 % (1 << arg2 + 1) - (1 << arg2) + 1)
for trie in range(int(input())):
	(n, m) = map(int, input().split())
	out_put = 0
	for i in range(0, 31):
		out_put = (out_put + (pow(coun(m, i), n) << i) % 998244353) % 998244353
	print(out_put)


import math

def count(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)

def power(b, n):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % 998244353
		b = b * b % 998244353
		n //= 2
	return s
for t in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	for i in range(31):
		s = (s + (power(count(m, i), n) << i) % 998244353) % 998244353
	print(s)


def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	mod = 998244353
	new = [0] * 32
	for i in range(31):
		new[i] = getcount(m + 1, i)
	for i in range(32):
		ans = (ans + (1 << i) * pow(new[i], n, mod) % mod) % mod
	print(ans)


MODULE = 998244353
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	ans = 0
	for i in range(M.bit_length()):
		suma = M // 2 ** (i + 1) * 2 ** i + max(M % 2 ** (i + 1) - 2 ** i + 1, 0)
		ans += 2 ** i * pow(suma, N, MODULE)
	print(ans % MODULE)


for k in range(int(input())):
	(n, i) = list(map(int, input().split()))
	s = 0
	for j in range(0, 32):
		q = (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
		s += pow(q, n, 998244353) << j
	print(s % 998244353)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	m1 = m
	c = 1
	xx = 1
	while 1:
		if m1 < xx:
			c -= 1
			break
		elif m1 == xx:
			break
		c += 1
		xx *= 2
	ans = 0
	p = 1
	k = {}
	h = 2
	for y in range(0, c):
		if (m + 1) % h == 0:
			l = (m + 1) // h
			l = l * (h // 2)
			k[y] = l
		else:
			l = (m + 1) // h
			l = l * (h // 2)
			r = (m + 1) % h
			if r <= h // 2:
				r = 0
			else:
				r = r - h // 2
			k[y] = l + r
		h *= 2
	f = {}
	n1 = n
	z = 998244353
	for q in range(c):
		n1 = n
		t = 1
		kk = k[q]
		while n1:
			if n1 & 1 == 1:
				t = t * kk % z
			n1 = n1 >> 1
			kk = kk * kk % z
		ans = ans + t * p
		p *= 2
	print(ans % z)


import math
beeg = 998244353

def beegPow(base, exponent):
	return pow(base, exponent, beeg)
for tea in range(int(input())):
	ans = 0
	(n, m) = [int(aaa) for aaa in input().split()]
	for i in range(math.floor(math.log2(m)) + 1):
		lawl = 2 ** i
		daNum = m // (2 * lawl) * lawl + max(0, m % (2 * lawl) - lawl + 1)
		ans = (ans + beegPow(daNum, n) * lawl) % beeg
	print(ans)


md = 998244353
t = int(input())
for _ in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	ans = 0
	for i in range(0, 32):
		ans += pow((m // pow(2, i + 1) << i) + max(0, m % pow(2, i + 1) - pow(2, i) + 1), n, md) << i
	print(ans % md)


mod = 998244353
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = [0 for i in range(31)]
	bi = str(bin(m))[2:][::-1]
	l1 = []
	for i in range(len(bi)):
		x = m >> i + 1
		x = x << i
		if bi[i] == '1':
			x = x + (m - (m >> i << i) + 1)
		l1.append(x)
	ans = 0
	c = 0
	for i in l1:
		ans += pow(i, n, mod) * pow(2, c, mod)
		c += 1
		ans = ans % mod
	print(ans)


import numpy as np
import math

def fgx(n):
	length = len(bin(n)[2:])
	array = [0] * length
	power = 2
	for i in range(0, length):
		array[i] = math.floor((n + 1) / power) * (power / 2) + max((n + 1) % power - power / 2, 0)
		power = power * 2
	return array

def calculate(n, m):
	array = np.array(fgx(n))
	mod = 998244353
	count = 0
	power = 1
	for x in array:
		count += power * pow(int(x), m, mod) % mod
		power = power * 2 % mod
	return count % mod
n = int(input())
for _ in range(0, n):
	array = list(map(int, input().split()))
	print(calculate(array[1], array[0]))


MOD = 998244353

def getex(till, exp):
	ex = till >> exp + 1 << exp
	powxp = 1 << exp
	if till & powxp:
		ex += till % powxp
	return ex

def main(N, M):
	summation = 0
	for exp in range(M.bit_length()):
		expenses = getex(M + 1, exp)
		expbitsum = (pow(expenses, N, MOD) << exp) % MOD
		summation = (summation + expbitsum) % MOD
	return summation
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	print(main(N, M))


for _ in range(int(input())):
	(n1, m) = map(int, input().split())
	sum = 0
	p = 1
	for i in range(31):
		n = n1
		z = max(m % (1 << i + 1) - (1 << i) + 1, 0) + (m // (1 << i + 1) << i)
		p = 1
		while n:
			if n % 2:
				p = p * z % 998244353
			z = z * z % 998244353
			n //= 2
		sum = (sum + (p << i)) % 998244353 % 998244353
	print(sum)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def find(m, k):
	sk = 1 << k
	c1 = m >> k + 1 << k
	c0 = c1 << 1
	return c1 + max(0, m + 1 - c0 - sk)
for t in range(int(input())):
	(n, m) = mi()
	ans = 0
	mod = 998244353
	for i in range(32):
		curr = find(m, i)
		if curr > 0:
			ans += (1 << i) * pow(curr, n, mod)
			ans %= mod
	print(ans)


inf = 998244353

def an(n, a):
	z = 1
	while n:
		if n % 2:
			z = z * a % inf
		a = a * a % inf
		n //= 2
	return z
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(31):
		c = (m // (1 << i + 1) << i) + max(0, m % (1 << i + 1) - (1 << i) + 1)
		ans = (ans + (an(n, c) << i) % 998244353) % 998244353
	print(ans)


MOD = 998244353

def modpow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def cardinalBitX1toM(M, bit):
	if M < bit:
		return 0
	elif M < bit << 1:
		return M - bit + 1
	return bit * (M // (bit << 1)) + cardinalBitX1toM(M % (bit << 1), bit)

def main(N, M):
	ANS = 0
	for i in range(30):
		ANS += (1 << i) * modpow(cardinalBitX1toM(M, 1 << i), N, MOD)
		ANS %= MOD
	return ANS
T = int(input().strip())
for _ in range(T):
	(N, M) = [int(x) for x in input().strip().split()[:2]]
	print(main(N, M))


def count(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
for _ in range(int(input())):
	(sa, me) = list(map(int, input().split()))
	sh = 0
	for i in range(0, 32):
		sh += pow(count(me, i), sa, 998244353) << i
	print(sh % 998244353)


mod = 998244353

def power(x, y):
	a = 1
	while y:
		if y & 1:
			a = a * x % mod
		x = x * x % mod
		y >>= 1
	return a

def func(m, j):
	upper = m >> j + 1
	ans = upper * 2 ** j
	if m & 1 << j:
		ans += m - (upper << j + 1) - 2 ** j + 1
	return ans
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	ans = 0
	for j in range(30):
		ans += power(func(m, j), n) * 2 ** j % mod
	print(ans % mod)


from itertools import product
output = []
for _ in range(int(input())):
	(N, M) = map(int, input().split(' '))
	ways = 0
	two_power = 1
	while two_power <= M:
		c = M // (two_power << 1) * two_power
		r = (M & (two_power << 1) - 1) - (two_power - 1)
		if r > 0:
			c += r
		ways += pow(c, N, 998244353) * two_power % 998244353
		two_power <<= 1
	output.append(ways % 998244353)
print('\n'.join(map(str, output)))


def count(i, j):
	return (i // (1 << j + 1) << j) + max(0, i % (1 << j + 1) - (1 << j) + 1)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	s = 0
	for i in range(0, 32):
		s += pow(count(m, i), n, 998244353) << i
	print(s % 998244353)


import math

def pos(n):
	if n < 0:
		return 0
	return n
t = int(input())
breh = 998244353
for i in range(t):
	(n, m) = [int(a) for a in input().split()]
	s = int(math.log2(m + 1)) + 1
	array = [0] * s
	for i in range(s):
		array[i] = m // 2 ** (i + 1) * 2 ** i % breh + pos(m % 2 ** (i + 1) - 2 ** i + 1)
	f = 0
	for l in range(s):
		f = (f + pow(array[l], n, breh) * pow(2, l, breh)) % breh
	print(f)


MOD = 998244353

def K(m, i):
	nai = 2 ** i
	naii = nai * 2
	return m // naii * nai + max(0, m % naii - (nai - 1))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	result = 0
	for i in range(32):
		result += pow(K(m, i), n, MOD) * 2 ** i
		result %= MOD
	print(result)