```go
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

const mod int64 = 998244353

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

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n uint64
		var m int
		fmt.Fscan(in, &n, &m)

		if m == 1 {
			fmt.Fprintln(out, int64(n%uint64(mod)))
			continue
		}
		if m >= 3 {
			if n%2 == 0 {
				k := int64((n / 2) % uint64(mod))
				ans := (k * ((k + 1) % mod)) % mod
				fmt.Fprintln(out, ans)
			} else {
				two := int64(((n + 1) / 2) % uint64(mod))
				ans := (two * two) % mod
				fmt.Fprintln(out, ans)
			}
			continue
		}

		// m == 2
		bitLen := 1
		if n > 0 {
			bitLen = bits.Len64(n)
		}
		L := bitLen - 1

		pow2 := make([]int64, L+1)
		pow2[0] = 1
		for i := 1; i <= L; i++ {
			pow2[i] = (pow2[i-1] * 2) % mod
		}

		var cnt [2][2]int64
		var sumY [2][2]int64
		cnt[0][0] = 1

		for i := 0; i <= L; i++ {
			nBit := int((n >> uint(i)) & 1)
			var ncnt [2][2]int64
			var nsum [2][2]int64
			for c := 0; c <= 1; c++ {
				for p := 0; p <= 1; p++ {
					if cnt[c][p] == 0 {
						continue
					}
					b := nBit ^ (p ^ c)
					nc := (p + b + c) >> 1
					if b == 1 {
						toC, toP := nc, 0
						ncnt[toC][toP] = (ncnt[toC][toP] + cnt[c][p]) % mod
						nsum[toC][toP] = (nsum[toC][toP] + sumY[c][p]) % mod
					} else {
						toC, toP := nc, 0
						ncnt[toC][toP] = (ncnt[toC][toP] + cnt[c][p]) % mod
						nsum[toC][toP] = (nsum[toC][toP] + sumY[c][p]) % mod

						toC, toP = nc, 1
						ncnt[toC][toP] = (ncnt[toC][toP] + cnt[c][p]) % mod
						add := (sumY[c][p] + (cnt[c][p]*pow2[i])%mod) % mod
						nsum[toC][toP] = (nsum[toC][toP] + add) % mod
					}
				}
			}
			cnt = ncnt
			sumY = nsum
		}

		K := cnt[0][0] % mod
		S := sumY[0][0] % mod
		nmod := int64(n % uint64(mod))
		ans := (K*nmod - (2*S)%mod) % mod
		if ans < 0 {
			ans += mod
		}
		fmt.Fprintln(out, ans)
	}
}
```