Hôm nay rảnh việc, Hạo không có gì làm nên đã đưa ra những câu hỏi cho các em.

Với mỗi câu hỏi, các em nhận được một số nguyên dương \(N\), Hạo yêu cầu tính phần dư của tích các ước số của \(N\) khi chia cho \(998244353\).

Các em hãy trả lời tất cả câu hỏi của Hạo.

Input

• Dòng đầu tiên, chứa số nguyên dương \(T\) là số câu hỏi của Hạo
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương

Output

• Gồm \(T\) dòng.
• Mỗi dòng chứa một số nguyên dương là câu trả lời cho các câu hỏi theo thứ tự tương ứng đầu vào.

Ràng buộc:

• Có \(30%\) số lượng test thỏa mãn điều kiện: \(T \le 10^5 , N \le 10^3\);
• Có \(30%\) số lượng test khác thỏa mãn điều kiện: \(T \le 10^5 , N \le 10^5\);
• Có \(40%\) số lượng test khác thỏa mãn điều kiện: \(T \le 10^5 , N \le 10^7\);

Sample input

3
5
10
2986178

Sample out

5
100
856178939

Giải thích ví dụ:

• \(5\) có \(2\) ước số là \(1\) và \(5\) -> tích các ước số của \(5 = 1 \times 5 = 5\).
• \(10\) có \(4\) ước số là \(1, 2, 5\) và \(10\) -> tích các ước số của \(10 = 1 \times 2 \times 5 \times 10 = 100\).
• Phần dư của tích các ước số của \(2986178\) khi chia cho \(998244353\) là \(856178939\).