package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353
const MAX_K = 125

var pow2 [200]int64

func init() {
	pow2[0] = 1
	for i := 1; i < 200; i++ {
		pow2[i] = (pow2[i-1] * 2) % MOD
	}
}

func power(base, exp int64) int64 {
	res := int64(1)
	base %= MOD
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

func get_G(v int64, d int, n int64) int64 {
	if v > n {
		return 0
	}
	if d >= 62 || v > (n>>d) {
		return 0
	}
	L := v << d
	R := ((v + 1) << d) - 1
	if R > n || R < L {
		R = n
	}
	return R - L + 1
}

func F(h int, x int) int64 {
	if h < 0 {
		return 0
	}
	if x == 0 {
		return 1
	}
	ans := int64(0)
	if x <= h {
		ans = (ans + pow2[x]) % MOD
	}
	min_d := x - 1 - h
	if min_d < 0 {
		min_d = 0
	}
	max_d := x - 2
	if max_d > h-1 {
		max_d = h - 1
	}
	if min_d <= max_d {
		T := int64(max_d-min_d+1) % MOD
		term := (T * pow2[x-2]) % MOD
		ans = (ans + term) % MOD
	}
	return ans
}

func solve(in *bufio.Reader, out *bufio.Writer) {
	var n, m int64
	fmt.Fscan(in, &n, &m)

	S_prime := make([]int64, MAX_K+1)
	for v := int64(1); v < m; v++ {
		p := int64(1)
		for k := 1; k <= MAX_K; k++ {
			p = (p * v) % MOD
			S_prime[k] = (S_prime[k] + p) % MOD
		}
	}

	H := 0
	for (int64(1) << H) <= n {
		H++
	}
	H--

	c := make([]int64, MAX_K+1)

	for x := 0; x < MAX_K; x++ {
		k := x + 1
		for l := 0; l <= H; l++ {
			u_l := n >> (H - l)

			var p_ul int64 = 0
			if x == 0 {
				p_ul = 1
			} else {
				g_left := get_G(2*u_l, x-1, n) % MOD
				g_right := get_G(2*u_l+1, x-1, n) % MOD
				p_ul = (g_left + g_right) % MOD

				for d := 0; d <= x-2; d++ {
					g1 := get_G(2*u_l, d, n) % MOD
					g2 := get_G(2*u_l+1, x-2-d, n) % MOD
					p_ul = (p_ul + g1*g2) % MOD
				}
			}
			c[k] = (c[k] + p_ul) % MOD

			CL := u_l - (int64(1) << l)
			if CL > 0 {
				CL_mod := CL % MOD
				f_val := F(H-l, x)
				c[k] = (c[k] + CL_mod*f_val) % MOD
			}

			max_node := (int64(1) << (l + 1)) - 1
			if max_node > n || max_node < 0 {
				max_node = n
			}
			CR := max_node - u_l
			if CR > 0 {
				CR_mod := CR % MOD
				f_val := F(H-1-l, x)
				c[k] = (c[k] + CR_mod*f_val) % MOD
			}
		}
	}

	n_mod := n % MOD
	pairs := (n_mod * ((n_mod + 1) % MOD)) % MOD
	pairs = (pairs * 499122177) % MOD 

	ans := (pairs * power(m, n+1)) % MOD

	for k := 1; k <= MAX_K; k++ {
		if c[k] == 0 {
			continue
		}
		term := c[k]
		if n >= int64(k) {
			term = (term * power(m, n-int64(k))) % MOD
		}
		term = (term * S_prime[k]) % MOD
		ans = (ans - term + MOD) % MOD
	}

	fmt.Fprintln(out, ans)
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}
	for i := 0; i < t; i++ {
		solve(in, out)
	}
}