Tokitsukaze and Multiple

Problem Description

Tokitsukaze has a sequence of length $n$, denoted by $a$. Tokitsukaze can merge two consecutive elements of $a$ as many times as she wants. After each operation, a new element that equals to the sum of the two old elements will replace them, and thus the length of $a$ will be reduced by $1$. Tokitsukaze wants to know the maximum possible number of elements that are multiples of $p$ she can get after doing some operations (or doing nothing) on the sequence $a$.

Input

There are several test cases. The first line contains an integer $T$ $(1 \leq T \leq 20)$, denoting the number of test cases. Then follow all the test cases. For each test case, the first line contains two integers $n$ and $p$ $(1 \leq n, p \leq 10^5)$, denoting the length of the sequence and the special number, respectively. The second line contains $n$ integers, where the $i$-th integer $a_i$ $(1 \leq a_i \leq 10^5)$ is the $i$-th element of $a$. It is guaranteed that the sum of $n$ in all test cases is no larger than $10^6$.

Output

For each test case, output in one line the maximum possible number of elements that are multiples of $p$ after doing some operations.

Sample Input

2
5 3
2 1 3 2 1
3 1
123 456 789

Sample Output

3
3

Source

2020 Multi-University Training Contest 3