D. Kings Game (Hard Version)

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

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$ 取模。

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

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

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

对于每组数据：

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

第二行，$n$ 个整数 $b_1,\dots,b_n(1\le b_i\le 10^7)$，代表国王B取来的数组。

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

保证同一测试点内 $n$ 的总和不超过 $10^6$ 且 $q$ 的总和不超过 $10^6$。

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

输入样例

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