#include <iostream>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cstring>
#include <numeric>
#include <vector>

using namespace std;

int dollCount, childCount;
vector<int> dolls;

int waysToBuy(const vector<int>& psum, int k){
    const int MOD = 20091101;
    int ret = 0;
    vector<long long> count(k, 0);
    for (int i = 0; i < psum.size(); i++){
        count[psum[i]]++;
    }

    for (int i = 0; i < k; i++){
        if (count[i] >= 2){
            ret = (ret + ((count[i] * (count[i - 1] - 1)) / 2)) % MOD;
        }
    }
    return ret;
}

int maxBuys(const vector<int>& psum, int k){
    vector<int> ret(psum.size(), 0);
    vector<int> prev(k, -1);
    for (int i = 0; i < psum.size(); i++){
        if (i>0) ret[i] = ret[i - 1];
        else ret[i] = 0;

        int loc = prev[psum[i]];
        if (loc != -1) ret[i] = max(ret[i], ret[loc] + 1);
        prev[psum[i]] = i;
    }
    return ret.back();
}

int main(){
    int testCase;
    cin >> testCase;
    for (int t = 0; t < testCase; t++){
        cin >> dollCount >> childCount;
        dolls.resize(dollCount);
        vector<int> psum(1, 0);
        for (int i = 0; i < dollCount; i++){
            cin >> dolls[i];
            psum.push_back((dolls[i] + psum.back()) % childCount);
        }

        cout << waysToBuy(psum, childCount) << " " << maxBuys(psum, childCount) << endl;
    }
    return 0;
}