Mystic Subarray Sums

Deep in the ancient lands of Numeria, the wizards discovered a magical array forged by celestial architects. According to legend, every contiguous segment (or subarray) of this array hides a secret power. The scrolls state that a subarray is truly mystical if the sum of its elements is divisible by a given divine number $K$. Your quest is to help the wizards count the number of such mystical subarrays in the given array.

Given an array of $N$ integers and an integer $K$, determine how many subarrays have a sum that is a multiple of $K$ (i.e., the sum is divisible by $K$).

Input Format

• The first line contains a single integer $T$, representing the number of test cases.
• For each test case, the first line contains two space-separated integers $N$ and $K$, where:
  • $N$ is the number of elements in the array.
  • $K$ is the mystical divisor.
• The second line of each test case contains $N$ space-separated integers representing the elements of the array.

Output Format

For each test case, print a single integer on a new line — the number of subarrays whose sum is divisible by $K$.

Examples

Input

1
5 3
1 2 3 4 1

Output

4

Input

2
4 2
1 2 3 4
3 5
5 5 5

Output

4
6