题目内容

在一个环形监测阵列中，有 $n$ 个站点，编号为 $1$ 到 $n$。第 $i$ 个站点记录一个整数偏移量 $a_i$。站点按环形排列，编号 $n$ 的后继是编号 $1$。

给定一个正整数 $K$。对于每个起点 $s$（$1 \le s \le n$），从站点 $s$ 开始，沿环依次读取偏移量。设无限序列 $b_1,b_2,\dots$ 为 $a$ 的循环延拓，即

对于步数 $t \ge 1$，定义第 $t$ 步的检测码为

其中取模结果为标准余数，落在区间 $[0,K-1]$ 内。

起点 $s$ 的最长有效步数 $L_s$ 定义如下：在不超过 $n$ 步的范围内，检测码 $C_1,C_2,\dots,C_{L_s}$ 必须两两不同。如果 $L_s < n$，则再取第 $L_s+1$ 步时会出现与之前某个检测码相等的检测码；如果 $L_s = n$，表示已经取满全部 $n$ 步。检测码只统计 $t \ge 1$ 的值，出发前状态不计入，因此 $L_s$ 至少为 1。

请计算所有起点的最长有效步数之和：

数据约束：测试数据组数不超过 10^5；序列长度 $n$ 和参数 $K$ 均不超过 2 × 10^5；每个偏移量 $a_i$ 的绝对值不超过 10^9；所有测试数据的 $n$ 之和不超过 2 × 10^5。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^5$），表示测试组数。每组测试数据描述如下：

• 第一行输入两个整数 $n$ 和 $K$（$1 \le n \le 2 \times 10^5$，$1 \le K \le 2 \times 10^5$）。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9 \le a_i \le 10^9$）。 保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示该组数据所有起点的最长有效步数之和 $\sum_{s=1}^{n} L_s$。

样例1

输入

2
3 5
1 1 1
4 6
2 -1 2 -1

输出

9
14

说明

第一组 $n=3$、$K=5$、$a=[1,1,1]$。前缀余数从 $P_0=0$ 开始为 $P_1=1$、$P_2=2$、$P_3=3$、$P_4=4$、$P_5=0$。

起点 1 的窗口 $P_1,P_2,P_3$ 为 1,2,3，全部互不相同，因此 $L_1=3$。起点 2 的窗口 $P_2,P_3,P_4$ 为 2,3,4，也全部互不相同，$L_2=3$。起点 3 的窗口 $P_3,P_4,P_5$ 为 3,4,0，也全部互不相同，$L_3=3$。该组总和为 $3+3+3=9$。

第二组 $n=4$、$K=6$、$a=[2,-1,2,-1]$。前缀余数为 $P_1=2$、$P_2=1$、$P_3=3$、$P_4=2$、$P_5=4$、$P_6=3$、$P_7=5$。

起点 1 的窗口 $P_1,P_2,P_3,P_4$ 为 2,1,3,2，从左往右读到第 4 个时 2 重复，所以 $L_1=3$。起点 2 的窗口为 1,3,2,4，全部不同，所以 $L_2=4$。起点 3 的窗口为 3,2,4,3，第 4 个 3 重复，$L_3=3$。起点 4 的窗口为 2,4,3,5，全部不同，$L_4=4$。该组总和为 $3+4+3+4=14$。

样例2

输入

1
1 10
7

输出

1

说明

边界情况：只有一个站点 $n=1$。

此时只能走最多 1 步，检测码为 $C_1=a_1 \bmod K=7 \bmod 10=7$。没有更长的可选步数，因此 $L_1=1$，总和为 1。