불균형

과학자들이 특이한 방식으로 번식하는 새로운 박테리아 종을 발견했다. 방 안에 박테리아가 $x$마리 있을 때, 매 분마다 텔레파시 통신이 한 번 이루어지고, 그 뒤 그중 한 마리가 분열하도록 선택된다. 각 박테리아가 선택될 확률은 $1 / x$로 같다.

과학자들은 이 분열 전략이 얼마나 균형 잡혀 있는지 알고 싶어 했다. 그들은 방에 페트리 접시 $n$개를 놓았고, 각 접시에는 박테리아가 정확히 1마리씩 들어 있었다. 분열할 때마다 다음과 같이 계수 $d$를 계산했다. 어느 한 접시의 박테리아 수가 다른 모든 접시의 박테리아 수를 합한 것보다 많으면, $d$는 두 수의 차이로 한다. 그렇지 않으면 $d$는 $0$이다. 형식적으로, 접시의 박테리아 수가 $a_1 \ge a_2 \ge \ldots \ge a_n$이면 $d = \max(a_1 - a_2 - \ldots - a_n, 0)$이다.

첫 번째 분, 두 번째 분, $\ldots$, $k$번째 분 이후의 $d$ 값을 모두 더한 합의 기댓값을 구하라. 답은 서로소인 정수 $p$, $q$에 대해 $\frac{p}{q}$ 꼴로 쓸 수 있으며 $q \not\equiv 0 \pmod{998\,244\,353}$이다. $r \cdot q \equiv p \pmod{998\,244\,353}$을 만족하는 정수 $r$을 출력하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 3 \cdot 10^5$)가 주어진다. 이어지는 $t$줄에는 각각 두 정수 $n$, $k$ ($1 \le n, k \le 10^6$)가 주어진다. 모든 테스트 케이스의 $n$과 $k$의 총합은 $2 \cdot 10^6$ 이하이다.

각 테스트 케이스마다 한 줄에 정수 $r$을 출력한다. 여기서 $r \cdot q \equiv p \pmod{998\,244\,353}$이고, $\frac{p}{q}$는 첫 번째 분부터 $k$번째 분까지의 $d$ 값들의 합의 기댓값이다.