J. 过程淘汰II
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

在深圳的 T3 教学楼，有一个空间异常：这里没有 3 楼。无论是乘坐电梯还是步行楼梯，空间都会直接从 2 楼跳跃到 4 楼。

据说，这是由于 T3 的空间场域极度不稳定，连接任意两个位置的通路，都会被路径上最薄弱的"瓶颈"所主导。这一现象也被称为"过程淘汰"。

为了研究这一现象，你记录了 T3 走廊上 N 个观测点的能量值序列 A，并试图计算在不同维度下的"总淘汰代价"。

我们发现空间的不稳定性主要源于物质的基本构成。因此，我们将针对 K 的每一个质因子（Prime Factor）p，分别计算该维度下的淘汰代价，并将所有结果累加。

对于 K 的每一个质因子 p，定义当前维度的投影序列 B，其中 。 在序列 B 上，对于任意两个位置 i 和 j (1 ≤ i < j ≤ N)，它们之间会产生一个淘汰代价 Costp(i, j)，计算规则如下：

  1. 确定淘汰点： 考察闭区间 [i, j] 内的所有数值，找到值最小的位置。 根据 T3 的"先序优先"法则，如果存在多个位置的值都等于最小值，我们取下标最小（最左侧）的那个位置作为"淘汰点"，记为 pos。
  2. 计算代价： 位置 i 和 j 之间的淘汰代价由两端的能量差异（异或和）与淘汰点的能量共同决定：

形式化地，你需要求解的答案 Ans 定义如下：

其中：

  • 表示 p 是 K 的质因子（例如：若 K = 12，则质因子为 2 和 3）。
  • 表示按位异或运算 (Bitwise XOR)。
  • mint = ij(...) 表示取区间[l, r]内的最小值（若有多个最小值，取下标最小的对应值）。
  • 表示所有满足 l ≤ x ≤ r 的整数 x 构成的闭区间（例如：若 [1, 4]，则区间包含整数 1, 2, 3, 4）。
Input

第一行输入一个整数 t (1 ≤ t ≤ 1000)，表示测试数据组数。

对于每组测试数据： 第一行输入两个整数 N 和 K (1 ≤ N ≤ 5 × 105, 2 ≤ K ≤ 108)，分别表示序列长度和场域参数。 第二行输入 N 个整数 A1, A2, ..., AN (1 ≤ Ai ≤ 109)，表示观测点的能量值。

保证所有测试数据的 N 之和不超过 5 × 105。

Output

对于每组测试数据，输出一行一个整数，表示总淘汰代价对 998244353 取模后的结果。

Example
Input
3
5 6
2 5 1 6 3
6 10
2 2 5 3 1 1
1 6
9
Output
6
4
0
Note

对于第一组样例，N = 5, K = 6，质因子为 2 和 3。

  • 当 p = 2 时，投影序列 B = {0, 1, 1, 0, 1}。经计算，所有区间的淘汰代价均为 0。
  • 当 p = 3 时，投影序列 B = {2, 2, 1, 0, 0}。其中：
    • 区间 [1, 3] (对应值 2, 2, 1) 的最小值为 1 (下标 3)，代价为 。
    • 区间 [2, 3] (对应值 2, 1) 的最小值为 1 (下标 3)，代价为 。
    • 其他区间代价均为 0。
    该维度总代价为 6。
最终答案为 0 + 6 = 6。

对于第二组样例，N = 6, K = 10，质因子为 2 和 5。

  • 当 p = 2 时，总代价为 0。
  • 当 p = 5 时，投影序列 B = {2, 2, 0, 3, 1, 1}。非零贡献来自：
    • 区间 [4, 5] (值 3, 1)，最小值为 1，代价 。
    • 区间 [4, 6] (值 3, 1, 1)，最小值为 1 (下标 5)，代价 。
    该维度总代价为 4。
最终答案为 0 + 4 = 4。