Submission #78

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while(T--){
        int N, K; cin >> N >> K;
        vector<long long> arr(N);
        for (int i=0; i<N; i++) cin >> arr[i];
        unordered_map<int, long long> freq;
        long long prefix = 0, ans = 0;
        freq[0] = 1;
        for (int i=0; i<N; i++){
            prefix += arr[i];
            int rem = (int)((prefix % K + K) % K);
            ans += freq[rem];
            freq[rem]++;
        }
        cout << ans << "\n";
    }
    return 0;
}