#include <iostream>
#include <numeric>
#include <map>

using namespace std;

void calculate_partial_sums(unsigned int *D, int N, int K, unsigned int *partial_sums);
unsigned int get_possible_purchase_number(int N, int K, unsigned int *partial_sums);
int get_max_purchase_number(int N, int K, unsigned int *partial_sums);

const int MAX_N = 100000;

int main() {
    int T;
    int N, K;
    int Di;
    unsigned int *D, *partial_sums;

    cin >> T;
    while (T-- > 0) {
        cin >> N >> K;

        D = new unsigned int[N];
        partial_sums = new unsigned int[N + 1];

        for (int i=0; i<N; ++i) {
            scanf("%d", &Di);

            D[i] = Di;
        }

        calculate_partial_sums(D, N, K, partial_sums);
        cout << get_possible_purchase_number(N, K, partial_sums) << " " << get_max_purchase_number(N, K, partial_sums) << endl;

        delete[] D;
        delete[] partial_sums;
    }

    return 0;
}

void calculate_partial_sums(unsigned int *D, int N, int K, unsigned int *partial_sums) {
    partial_sums[0] = 0;
    for (int i=1; i<=N; ++i) {
        partial_sums[i] = (partial_sums[i-1] + D[i-1]) % K;
    }
}

unsigned int get_possible_purchase_number(int N, int K, unsigned int *partial_sums) {
    unsigned int possible_purchase_number = 0;
    map<int, unsigned int> occurance;
    map<int, unsigned int>::iterator iter;

    for (int i=0; i<=N; ++i) {
        if ((iter = occurance.find(partial_sums[i])) != occurance.end()) {
            iter->second++;
        } else {
            occurance.insert(make_pair(partial_sums[i], 1));
        }
    }

    for (iter=occurance.begin(); iter!=occurance.end(); ++iter) {
        possible_purchase_number += ((iter->second * (iter->second - 1)) / 2) % 20091101;
        possible_purchase_number %= 20091101;
    }

    return possible_purchase_number;
}

int get_max_purchase_number(int N, int K, unsigned int *partial_sums) {
    int max_purchase_numbers[MAX_N + 1];
    int same_partial_sums[MAX_N + 1];

    for (int i=0; i<=MAX_N; ++i) {
        max_purchase_numbers[i] = 0;
        same_partial_sums[i] = -1;
    }

    for (int i=0; i<=N; ++i) {
        if (i > 0) {
            max_purchase_numbers[i] = max_purchase_numbers[i-1];
        } else {
            max_purchase_numbers[i] = 0;
        }

        if (same_partial_sums[partial_sums[i]] != -1) {
            max_purchase_numbers[i] = max(max_purchase_numbers[i], 1 + max_purchase_numbers[same_partial_sums[partial_sums[i]]]);
        }

        same_partial_sums[partial_sums[i]] = i;
    }

    return max_purchase_numbers[N];
}