Description

给出 $N$，求：

$$\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1]$$

答案模 $998244353$。

$[]$ 是条件表达式。当括号里面的式子成立时值为 $1$，否则为 $0$。

Input Format

仅一行一个整数，为 $N$。

Output Format

输出一个整数，为所求答案模上 $998244353$ 的值。

50

104527

200

6664993

500000

835964450

10000000

503290049

100000000

712748411

1000000000

845640070

Hint

对于所有数据，保证 $1\le N\le 2\times10^9$，所有测试点的时限均为 $1\text{s}$，空间限制均为 $500\text{MB}$。

测试点编号	$N$
$1$	$\le 100$
$2$	$\le 400$
$3,4,5,6$	$\le10^6$
$7,8$	$\le 2\times10^7$
$9$	$\le 2\times10^8$
$10$	$\le 2\times10^9$

这题其实可以搞一个测试点多组数据，但良心的出题人为了多给你们一点部分分，就决定只来一组数据。

idea 源自 @Fee_cle6418，题目的题面，标算，数据源自 @FangZeLi。