1006. Gcd Master

题目描述

给定 $n$，求

$$\sum_{i=1}^n\sum_{j=i}^n\sum_{k=i}^j\gcd(i,k)\gcd(j,k){j \choose k}$$

对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。

之后 $T$ 行，每行包含一个整数 $n$（$1 \le \sum n \le 5 \times 10^5$）。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

样例输入

1
5

样例输出

298

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1006