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 ```