7461: Tokitsukaze and Multiple

Tokitsukaze has a sequence of length n, denoted by a.
Tokitsukaze can merge two consecutive elements of aas 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 awill be reduced by 1.
Tokitsukaze wants to know the maximum possible number of elements that are multiples of pshe can get after doing some operations (or doing nothing) on the sequence a.

There are several test cases.
The first line contains an integer T(1≤T≤20), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains two integers nand p(1≤n,p≤105), denoting the length of the sequence and the special number, respectively.
The second line contains nintegers, where the i-th integer ai(1≤ai≤105)is the i-th element of a.
It is guaranteed that the sum of nin all test cases is no larger than 106.

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