You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

你见过 $n$ 面的骰子吗? 我反正是没见过.

题目描述

给你一个 $n$ 面的骰子, 我们可以等概率的骰出 $1 \dots n$ 之间的数值, 现在你要投掷骰子, 如果投掷出的数值为质数, 你需要重新投掷, 否则就停止, 我们想知道你投掷骰子的期望值是多少?

注意: 答案需要对那个经典数字取模, 没错就是 998244353.

输入格式

第一行一个整数 $t$，表示有 $t$ 组数据

接下来 $t$ 行, 每行一个整数 $n$, 表示骰子的面数为 $n$.

输出格式

输出 $t$ 行, 每行一个整数表示投掷出数值的期望值.

样例 #1

样例输入 #1

5
1
2
5
1000000
10000000

样例输出 #1

1
1
499122179
172029425
211810305

提示

$1 \le t \le 1000$

$1 \le n \le 10^7$