```go
package main

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

const MOD int64 = 998244353
const inv2 int64 = (MOD + 1) / 2
const maxL int = 130

type State struct {
	dist  []int64
	total int64
	up    int64
}

func modPow(a, e, mod int64) int64 {
	res := int64(1)
	a %= mod
	for e > 0 {
		if e&1 == 1 {
			res = res * a % mod
		}
		a = a * a % mod
		e >>= 1
	}
	return res
}

func combine(a, b State, g []int64) State {
	maxLen := len(a.dist)
	if len(b.dist) > maxLen {
		maxLen = len(b.dist)
	}
	newDist := make([]int64, maxLen+1)
	newDist[0] = 1
	for i := 0; i < maxLen; i++ {
		var cnt int64
		if i < len(a.dist) {
			cnt += a.dist[i]
		}
		if i < len(b.dist) {
			cnt += b.dist[i]
		}
		newDist[i+1] = cnt % MOD
	}

	total := (a.total + b.total) % MOD
	total = (total + g[1]) % MOD

	for d, cnt := range a.dist {
		L := d + 2
		if L < len(g) {
			total = (total + cnt*g[L]) % MOD
		}
	}
	for d, cnt := range b.dist {
		L := d + 2
		if L < len(g) {
			total = (total + cnt*g[L]) % MOD
		}
	}
	for d1, cnt1 := range a.dist {
		for d2, cnt2 := range b.dist {
			L := d1 + d2 + 3
			if L < len(g) {
				total = (total + cnt1*cnt2%MOD*g[L]) % MOD
			}
		}
	}

	up := g[2]
	for d, cnt := range a.dist {
		L := d + 3
		if L < len(g) {
			up = (up + cnt*g[L]) % MOD
		}
	}
	for d, cnt := range b.dist {
		L := d + 3
		if L < len(g) {
			up = (up + cnt*g[L]) % MOD
		}
	}

	return State{dist: newDist, total: total, up: up}
}

func solve() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)
	for tc := 0; tc < t; tc++ {
		var n int64
		var m int
		fmt.Fscan(reader, &n, &m)

		S := make([]int64, maxL+1)
		for y := 0; y < m; y++ {
			p := int64(1)
			y64 := int64(y)
			for k := 0; k <= maxL; k++ {
				S[k] = (S[k] + p) % MOD
				p = p * y64 % MOD
			}
		}

		pow_m_n := modPow(int64(m), n, MOD)
		inv_m := modPow(int64(m), MOD-2, MOD)
		inv_m_pow := int64(1)
		g := make([]int64, maxL+1)
		for L := 1; L <= maxL; L++ {
			inv_m_pow = inv_m_pow * inv_m % MOD
			g[L] = pow_m_n * inv_m_pow % MOD * S[L] % MOD
		}

		perfect := make([]State, 61)
		perfect[0] = State{
			dist:  []int64{1},
			total: g[1],
			up:    g[2],
		}
		for h := 1; h <= 60; h++ {
			perfect[h] = combine(perfect[h-1], perfect[h-1], g)
		}

		memo := make(map[int64]State)
		var dfs func(int64) State
		dfs = func(i int64) State {
			if i > n {
				return State{}
			}
			if st, ok := memo[i]; ok {
				return st
			}

			h := 0
			cur := i
			for cur <= n/2 {
				h++
				cur *= 2
			}
			if (i+1)<<h <= n+1 {
				memo[i] = perfect[h]
				return perfect[h]
			}

			left := dfs(i * 2)
			var right State
			if i*2+1 <= n {
				right = dfs(i*2 + 1)
			}
			state := combine(left, right, g)
			memo[i] = state
			return state
		}

		result := dfs(1)
		totalPairsSum := result.total

		nMod := n % MOD
		term1 := modPow(int64(m), n+1, MOD)
		term1 = term1 * nMod % MOD
		term1 = term1 * ((nMod + 1) % MOD) % MOD
		term1 = term1 * inv2 % MOD

		ans := (term1 - totalPairsSum) % MOD
		if ans < 0 {
			ans += MOD
		}
		fmt.Fprintln(writer, ans)
	}
}

func main() {
	solve()
}
```