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.