8653: Leapfrogger

Notice: If you have played Battlegrounds in Hearthstone and know the mechanism of leapfrogger and Baron Rivendare, you can start at the fourth paragraph, but note that the context of the problem is simplified and may not be the same as what is in-game.

In the famous card-collecting game Hearthstone, there is a mode named Battlegrounds, based on the auto battler genre, and allows eight players to compete in each match by recruiting minions over several rounds. In Battlegrounds, there is a special minion named leapfrogger, which is a second-tier beast with stats 3/3, and has the deathrattle of "Give a friendly beast +1/+1 and this deathrattle'', which means that when this minion dies, it will randomly give a friendly beast (if there exists any) the effect of +1/+1 in stats and this same effect (i.e., when that friendly beast dies, it will randomly give a friendly beast +1/+1 and the same effect, et cetera).

An interesting thing about leapfrogger is that its deathrattle is stackable, i.e., a minion is allowed to have multiple, say $k$, deathrattles of the leapfrogger at the same time, then when this minion dies, it will randomly give a friendly beast(if there exists any) the effect of +1/+1 in stats and this same effect, repeated $k$ times. Note that in each of the $k$ times, the friendly beast is chosen independently at random. What makes things more interesting is a minion in Battlegrounds called Baron Rivendare that can double the effect of deathrattles when it is on the board. When Baron Rivendare is on the board, and a leapfrogger dies, its deathrattle is triggered and given to a random friendly beast, twice. If both deathrattles are given to the same friendly beast and that beast dies, still with Baron Rivendare on the board, each of the two deathrattles of leapfrogger on the beast is triggered twice, so that a total of four copies of the deathrattle of leapfrogger are triggered and given to a random friendly beast... The speed the deathrattle of leapfrogger spread when Baron Rivendare is on the board is quite insane and is what makes the "leapfrogger build" a possible and quite powerful strategy in Battlegrounds.

That is quite a lot for the background. Let's then make some simplifications. We assume the deathrattle of leapfrogger can be given to any minion instead of only to beasts. We also assume that ALL Deathrattles will be triggered $k$ times for the sake of the problem. The question is,

1. There are $n$ minions on the board with exactly one of them being leapfrogger. If you kill all the n minions in a random order, how many times in expectation will the deathrattle of the leapfrogger be triggered? (Recall that all deathrattles will be triggered k times), answer the question for all k=2,3,...,m for some given parameter $m$. Note that the deathrattles on the last minion still count as triggered, even if they are not given to another minion.

The first line contains an integer $T(1\le T\le 10)$, denoting the number of test cases.

For each test case, the input consists of one line containing two integers n,m. (1≤n<998244353,2≤m≤105), denoting the number of minions and the parameter, respectively.