题目描述

Y 同学写下正整数 $n$ 的所有正约数，并想从中选出一个非空子集 $S$。这个子集必须同时满足两个条件：所有元素的最大公约数为 $1$，所有元素的最小公倍数为 $n$。

不同的约数集合视为不同方案。给定多组 $n$，请统计合法非空子集数量，答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $q$。

接下来 $q$ 行，每行一个整数 $n$。

输出格式

对每个询问输出一行一个整数，表示合法子集数量。

样例

样例输入 #1

3
1
6
12

样例输出 #1

1
7
32

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le q\le25$，$1\le n\le10^{12}$。

特殊性质 A：保证 $n$ 为质数幂。 特殊性质 B：保证 $n$ 无平方因子。