背景

本题时间限制约为 std 的 $1.5\sim 2$ 倍，可能会有点卡常，请精细实现您的代码。

题目描述

定义 Fibonacci 序列 $f_n$ 满足 $f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)$。

现在给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，你需要对每个 $i=1,2,3,\ldots,n$ 都求出 $\operatorname{lcm}(f_{a_1},f_{a_2},\ldots,f_{a_i})\bmod 998244353$ 的值。

输入格式

第一行一个整数 $n$。

然后一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

一行 $n$ 个整数分别表示 $i=1,2,3,\ldots,n$ 时的答案。

3
3 4 6

2 6 24

7
1 9 8 9 1 2 10

1 34 714 714 714 714 39270

8
2 1 8 10 5 6 3 3

1 1 21 1155 1155 9240 9240 9240

提示

本题采用捆绑测试。

对于 $15\%$ 的分数满足 $n\le 1000$。

对于另外 $20\%$ 的分数满足 $a_i\le 10^6$。

对于另外 $25\%$ 的分数满足 $a_i$ 在 $[1,10^9]$ 范围内等概率均匀随机生成。

对于全部的分数满足 $1\le n\le 10^5,1\le a_i\le 10^9$。