You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

小 K 今天学习了如何做乘法，他想找个练习题进行练习，于是这道题诞生了。

Description

给你一个长度为 $n$ 的序列 $a$，再给你一个质数 $p$，请你求出有多少个区间 $[l,r]$ 满足：

$$\left(\prod_{i=l}^{r} a_i \right) \text{mod}~p=1$$

Format

Input

本题有多组数据。

第一行一个数字 $T$，表示数据组数。

每组数据由两行组成，第一行两个数字分别表示 $n$ 和 $k$，第二行 $n$ 个自然数，表示 $a$ 序列。

Output

输出共 $T$ 行，表示每组数据的答案。

Samples

2
9 7
2 2 2 2 2 2 2 2 2
9 3
4 4 3 3 4 4 3 3 4

12
7

Limitation

$T \leq 10$

对于 $20\%$ 的数据，满足 $n \leq 1000$

对于 $100\%$ 的数据，满足 $n \leq 10^5,a_i \leq 10^9,k \leq 10^9$