seuOJ554 - Kings Game (Hard Version)

题目描述

简单版和困难版的唯一区别是对于 n,qn,q 的限制条件不同，在简单版中 ∑n≤106;∑q≤106\sum n\le 10^6;\sum q\le 10^6。

Le perdant doit céder le terrain!

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

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

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

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

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

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

输入格式

第一行，一个整数 t(1≤t≤1000)t(1\le t\le 1000)，代表数据组数。

对于每组数据：

第一行，两个整数 n,q(1≤n≤106;1≤q≤106)n,q(1\le n \le 10^6;1 \le q\le 10^6)，代表国王B取来的数组长度和游戏次数。

第二行，nn 个整数 b1,…,bn(1≤bi≤107)b_1,\dots,b_n(1\le b_i\le 10^7)，代表国王B取来的数组。

接下来连续的 qq 行，每行两个整数 l,r(1≤l≤r≤n)l,r(1\le l\le r\le n)，代表当前这次游戏在子段 [bl,…,br][b_l,\dots,b_r] 上进行。

保证同一测试点内 nn 的总和不超过 10610^6 且 qq 的总和不超过 10610^6。

输出格式

对于每次询问，输出一行整数，代表国王A选取使得他自己能够赢得游戏的非空子序列的方案数，对于 998244353998244353 取模后的结果。

样例

输入样例

1
8 10
1 1 4 16 2 8 3 7
1 2
1 5
5 6
2 5
1 8
2 7
3 8
6 8
5 8
3 6

输出样例

3
27
2
13
223
55
55
5
11
13