問題文

青木くんはからくり仕掛けを作ろうとしています。

からくり仕掛けには歯車が必要ですが、歯車の損耗を抑えるためには噛み合う歯車の歯の数は互いに素である必要があります。

青木くんは高橋くんにそのような歯車の組合せがどれだけありうるか聞いてみることにしました。

正整数 $N$ が与えられます。

$N$ 以下の正整数のペア $\{x, y\}$ のうち、 $\text{gcd}(x, y) = 1$ であるものの数を求め、 $998244353$ で割ったあまりを答えてください。

ただし、順序を交換したペア、つまり、 $\{x, y\}$ と $\{y, x\}$ は同じものとみなします。

制約

• $1 \le N \le 5\times 10^5$
• 入力は整数である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

4

6

$4$ 以下の互いに素なペアには $\{1, 1\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{3, 4\}$ があります。

10

32

$32$ 個のペアが存在します。