# 2021 年东华大学金马程序设计联赛

F. It is Quite Big
PDF 题面可用

It was such a breaking news, which was spread among the high schools in our county like crazy.
Let me be clear first. I’m a junior, actually I used to be a weeaboo but now I rarely watch anime. Playing weeaboo games would be the furthest I can get. My classmate of junior high school, who started to watch animate together with me. now is in the very next class. We also often eat out and play together. There is a stupid weeaboo in his class. He watches anime and plays games every day in class, his grades are always the bottom in the class. I heard from my friend that he charged Arknights over tens of thousands yuan. Since there were very few people in his class who entered the house, he clung to my friends and often came in when we were eating together. But my friend and I have always disliked him. He often brags in front of us about what he has gotten while we don’t have this one, we also like to belittle other animes, without caring about our feeling at all. To belittle our favorite character.His character still has problems. He also has a poor reputation in his own class and has few friends.

At the beginning of last month, during the National Day holiday, he played Genshin Impact and charged 30,000 yuan. However, he was still not satisfied since the role was not full. He went to steal money and was caught by his father just on shot. He fought with his father and finally he took away fifty thousand and went back to school. Let me just say that my school is a full-time boarding school, with half-day holidays every Saturday and 2-3 days off at the end of each month. Then here is the things. When he returned home at the end of October, he found that his parents were not at home, only his sister was at home and his sister is playing The Legend of Zelda . He forced his sister playing Genshin Impact and threatened her not to tell her parents. At the beginning of this month, when he returned to school for lunch at the beginning of the month, he told us that his sister must be a mihoyo fans and she must like Keqing, so he force her playing genshin impact, even explained the details. At the time, my friend and I did not believe it. By the way, his sister was just 12.

At about 10 o’ clock the day before yesterday, his parents probably knew that he had forced his sister, so they ran to school and broke his leg on the spot. But he still said he would fight with his father till the last. At that time, many people recorded it and sent it to various high school chat groups. All high schools in our county knew about this incident, although the school has suppressed the news. Our school also spent half a day telling us not to spread the incident.

Anyway, they finally called up to the police. I don’t know what happened later, all I want to tell you is just stop being a weeaboo as soon as possible, do not become a person like him.

Now let we assumed $n=\prod_{i=1}^{m}p_i^{k_i}$, and $p_i$ are distinct prime numbers, $\Omega(n)=\sum_{i=1}^m k_i$, $\sigma(n)=\sum_{d|n}d$. Give you a postive number $n$, please calculate:
$$F(n)=\sum_{k=1}^n\sum_{d|k}(-1)^{\Omega(d)}\sigma(\frac{k}{d}) \pmod{998244353}, 1\leq n\leq 10^{18}$$

### 输入格式

The first line contains an integer $t$ ( $1 \le t \le 100$ ) — the number of test cases.

For each test case, there is only one line contains an integer $n$ ($1\leq n\leq 10^{18}$).

### 输出格式

For each test case, print a single line containing an integer indicate of answer module $998244353$.

### 样例

Input
3
23333
233333
2333333

Output
294638140
514198163
505851636


NaN