简单版和困难版的唯一区别是对于 $$$n,q$$$ 的限制条件不同，在简单版中 $$$\sum n\le 1000;\sum q\le 1000$$$。

Le perdant doit céder le terrain!

在公元四世纪的欧洲，有两个国王A和B，他们都很喜欢数学，所以它们就以66座城池为赌约，来进行一个游戏。游戏的内容如下。

有 $$$n$$$ 个正整数 $$$\{a_1,\dots,a_n\}$$$，在每次操作中，国王必须选择任意一个大于 $$$1$$$ 的正整数 $$$a_i$$$ 和及其一个大于 $$$1$$$ 的因子 $$$x$$$，使得 $$$a_i:=\frac{a_i}{x}$$$。显然当所有数字都变成 $$$1$$$ 时就无法进行任何操作，那么此时当前将要进行操作的国王获得游戏的胜利。且在每轮游戏中由国王A先进行操作，国王B后进行操作，两人轮流操作。

为了进行游戏，国王B拿来了一个数组 $$$[b_1,\dots,b_n]$$$ 并且和国王A商议后决定在每次都在数组 $$$b$$$ 的某一个子段 $$$[b_l,\dots,b_r]$$$ 上进行游戏。不过因为是国王B拿来的数组，在游戏前，国王A可以选择这个子段的某一个非空子序列来作为最终的游戏数组。对于即将进行游戏的某一个子段而言，他有多少种不同的选择非空子序列的方法，使得他可以赢得最终的游戏胜利。

由于选取子序列的方法数量很多，所以在输出答案时，请对 $$$998244353$$$ 取模。

子段是指数组中连续的元素序列，子序列是指从数组中按顺序选取的元素序列，但不要求连续。

对于两个子序列来说，称它们是不同的当且仅当它们的长度不同或者存在任意一个位置，使得这个位置在原数组中的下标不同。