题目背景

小 A：数论题真是无聊呢，一天到晚枚举二元组、三元组，太无聊了。

小 B：对呀对呀，都是套路。

小 A：要不我们试试枚举四元组？

小 B：......

于是就有了这道题。

题目描述

给出 $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$。

输入格式

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

输出格式

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

50

104527

200

6664993

500000

835964450

10000000

503290049

100000000

712748411

1000000000

845640070

提示

对于所有数据，保证 $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。