|
||||||||||
Tokitsukaze and MultipleTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 2155 Accepted Submission(s): 883 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
Sample Output
Source | ||||||||||
|