简单题

题目信息

时间限制: 3s

空间限制: 1024M

输入文件: easy.in

输出文件: easy.out

题目描述

对于 $\ge 2$ 的整数 $m$ 和正整数 $a$，定义 $f_m(a)$ 为 $[0,m)$ 内的整数 $x$ 的个数，满足 $x^a\equiv 1\pmod m$，且对于任何一个整数 $a'\in[1,a)$ 都有 $x^{a'}\not\equiv 1\pmod m$。也就是说，$f_m(a)$ 等于模 $m$ 意义下阶为 $a$ 的剩余类个数。

YeahPotato 现在给你了若干个 $m$，他希望你对于每个 $m$，回答最大的 $f_m(a)$，即 $\max_{a\in N_+}\set{f_m(a)}$。特殊地，当 $m=1$ 时，你只需要回答 $1$ 即可。

YeahPotato 将会用如下方式给出这些 $m$：初始时 $m=1$，每次他会将 $m$ 乘上或者除以一个质数（他保证 $m$ 时刻为正整数），你则要在每次修改后回答对应的最大值 $\bmod{998244353}$。

输入格式

第一行一个正整数 $q$，表示修改次数。

接下来 $q$ 行每行先是一个符号 + 或 -，然后一个正整数 $p$，保证 $p$ 为质数。符号与数之间不带空格，也就是可以直接当作有符号整数读入。若符号为 + 则表示将 $m$ 乘上 $p$，否则表示将 $m$ 除以 $p$。

输出格式

输出 $q$ 行，依次表示每次修改后的答案。

样例

样例输入 1

4
+2
+3
+2
-3

样例输出 1

1
1
3
1

样例解释 1

以第三次修改后的 $m=12$ 为例。注意有些数的幂次永远不可能等于 $1$，我们就将它忽略。

使得 $1^a\equiv 1\pmod{12}$ 的最小正整数 $a$ 为 $1$。

使得 $5^a\equiv 1\pmod{12}$ 的最小正整数 $a$ 为 $2$。

使得 $7^a\equiv 1\pmod{12}$ 的最小正整数 $a$ 为 $2$。

使得 ${11}^a\equiv 1\pmod{12}$ 的最小正整数 $a$ 为 $2$。

因此 $f_{12}(1)=1,f_{12}(2)=3$，其余的 $f_{12}(a)$ 值均为 $0$。

样例输入 2

9
+5
+7
+3
+3
+2
-5
+7
-3
+23333

样例输出 2

2
8
16
64
64
24
144
36
528768

样例输入 3

见下发文件夹中的 easy/easy3.in。

样例输出 3

见下发文件夹中的 easy/easy3.ans。

样例输入 4

见下发文件夹中的 easy/easy4.in。

样例输出 4

见下发文件夹中的 easy/easy4.ans。

数据范围与提示

上表中 $m\le M$ 表示任何时刻 $m$ 都 $\le M$，留空表示无限制。

特殊性质 A：输入只有正数。

特殊性质 B：输入除了的第一行外，其余行均相同。

对于 $100\%$ 的数据，$1\le q\le 5\times 10^5,2\le p\le 10^7$，保证 $p$ 为质数。