주사위 게임

푸타타와 부다다는 면이 $n$개인 주사위로 게임을 한다. $0$부터 $n-1$까지의 정수가 각각 정확히 한 면에 적혀 있고, 각 면이 위를 향할 확률은 모두 같다. 즉, 주사위를 던지면 $0$부터 $n-1$까지의 정수 중 하나가 균등한 확률로 나온다.

게임은 두 라운드로 진행된다. 첫 번째 라운드에서 푸타타가 주사위를 던져 나온 정수를 $x$라고 한다.

두 번째 라운드에서 부다다는 다음 중 하나를 선택할 수 있다.

• 게임을 끝낸다. 이때 점수는 $x$이다.
• 주사위를 한 번 더 던져 나온 값을 $y$라고 한다. 게임이 끝나고 점수는 $x \oplus y$이다. 여기서 $\oplus$는 비트 단위 배타적 논리합 연산이다.

푸타타와 부다다는 점수를 최대화하려 하며, 항상 최선의 선택을 한다. 주어진 $n$마다 게임 점수의 기댓값을 구하라.

답은 기약분수 $\frac{x}{y}$로 나타낼 수 있으며, $y \not\equiv 0 \pmod{998\,244\,353}$이다. $0 \leq a < 998\,244\,353$이고 $a \cdot y \equiv x \pmod{998\,244\,353}$을 만족하는 정수 $a$를 출력하라.

첫 줄에 정수 $T$ ($1 \leq T \leq 10^4$)가 주어진다. 이어지는 $T$개의 줄에는 각각 정수 $n$ ($1 \leq n \leq 998\,244\,352$)이 하나씩 주어진다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질문의 답을 출력한다.