A train conductor marks each compartment with a passenger mood score. A group of consecutive compartments is called lucky if the total mood score is divisible by K. Count how many lucky groups exist.

The twist: scores may be negative, so remainder handling must be careful.

The first line contains KaTeX can only parse string typed expression. For each test case, the first line contains KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. The second line contains KaTeX can only parse string typed expression integers.

For each test case, print the number of lucky subarrays. Print the output of each test-case in different lines.