★★序列大团结★★
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

热爱集体,向往团结。她喜欢一切团结的事物,例如团结的班级,团结的家庭,甚至是团结的序列。

认为,如果对于所有 ,都恰好满足以下条件之一:

  • 没有在序列 中出现过
  • 的倍数
  • 在序列 中的出现次数是 的倍数

那么就称序列 是团结的,其“团结因子”为

同时, 认为,对于一个“团结因子”为 的序列,其“团结度”为“团结因子”同样为 的不同非空连续子序列的数量。

一个序列的连续子序列为原序列中下标连续的任意子序列,即在原序列中截取了一段。例如 均是 的连续子序列,而 则不是。不同的连续子序列指的是从原序列中截取的位置不同,即使不同子序列中所包含数的大小和顺序可能完全相同。

想知道,对于一个给定的序列 和“团结因子” ,它的“团结度”是多少。

输入描述:

第一行一个整数 ,表示测试用例的数量。

对于每组测试用例,第一行两个整数 ,分别表示序列  的长度和“团结因子”;

接下来一行  个整数,第  个整数为 
对于全部测试用例,保证序列  在一定程度上随机生成,且 


输出描述:

对于每组测试用例,输出一行一个整数表示答案。
示例1

输入

复制
2
5 2
1 1 2 3 3
10 3
1 1 2 3 3 6 2 2 1 9

输出

复制
6
10

说明

在第一组测试用例中,团结的非空连续子序列有 ,团结度为 

在第二组测试用例中,团结度为