Count Sub-arrays with Sum Divisible by K

Given an array ARR and an integer K, determine the number of sub-arrays in which the sum is divisible by K.

Example:

Input:

ARR = {5, 0, 2, 3, 1}, K = 5

Output:

6

Explanation:

There are 6 sub-arrays whose sum is divisible by 5.

Constraints:

• 1 <= T <= 50
• 1 <= K, N <= 10^4
• -10^9 <= ARR[i] <= 10^9
• Time limit: 1 second

Input:

First line contains integer T indicating test cases.
For each test case, first line contains N and K.
Second line has N integers for the array ARR.

Output:

Output number of sub-arrays whose sum is divisible by K for each test case.

Note:

If no subarray exists with sum divisible by K, return 0.