题目描述

龙山的天气是醉人的温暖，恰好是樱花落尽的时季。散布着细沙的行人道上满是狼藉的粉色花片，有些便沾挂在平铺的碧草上。几树梨花还点缀着嫩白的残瓣。北面与西面小山上全罩着淡蓝色的衣校，小燕子来回在林中穿跳。在这里正是一年好景的残春，到处有媚丽的光景使人流连。
烟烟雾雾，云云霭霭。残春好景使人流连忘返，可是，在这伤春悲秋之时，即使柳树已经抽完了芽，青藤也换完了新枝，而鲜花已经不再盛开。明年的鲜花有，年年新花年年有，可是你曾今看到的那一朵，你永远无法挽留，即使深爱过，再也不会出现。
你引腕便要去挽，获得的只有眼角不受控落下的泪滴。你毅然步入梦中，映入眼帘的是一片开满着蓝色鸢尾花的田野。通过划分可以把这片田野化成无数块 ，第 i 块的面积为 i2 个单位面积，第 n 块的面积为 n2 个单位面积。每块蓝色鸢尾花田的排布以及面积如图所示：(红色数字 i 代表蓝色鸢尾花田编号，即第几块)
已知购买第 i 块蓝色鸢尾花田的一单位面积的价格 pricei 如下式所示：

如果 i 是 n 的因数，pricei = n/i，否则 pricei = n/i+1

现请你计算将前 n 片蓝色鸢尾花田全部购买下来所需要的价格。

输入

第一行输入一个正整数 t (1≤t≤100) ，表示有 t 组测试数据。
接下来 t 行，每行输入只有一个正整数 n (1≤n≤109) ，表示要购买的是前 n 片蓝色鸢尾花田。

输出

共有 t 行输出。
每行输出只有一个整数，表示将前 n 片蓝色鸢尾花田全部购买下来所需要的价格。输出可能很大，请你对 998244353 求余。

样例输入

5 1 3 1 4 1314520

样例输出

1 22 1 53 169351310

提示

1²+2²+...+n²=n(n+1)(2n+1)/6

对于样例 1 ：第一块蓝色鸢尾花田的单价是 1 ，面积为 1 ，故购买前 1 片蓝色鸢尾花田的总价格是 1×1=1 。
对于样例 2 ：第一块蓝色鸢尾花田的单价是 3 ，面积为 1 ；第二块蓝色鸢尾花田的单价是 5/2 ，面积为 4 ；第三块蓝色鸢尾花田的单价是 1 ，面积为 9 。故购买前 3 片蓝色鸢尾花田的总价格是 3×1+5/2×4+1×9=22 。

998244353是质数