#include<iostream>
#include<vector>
#define MOD 20091101
typedef long long ll;
using namespace std;
void p1(const vector<int> &cs, const int &n, const int &k) {
    vector<int> modu(k, 0);
    int i;
    modu[0] = 1;
    for (i = 1; i <= n; i++) {
        modu[cs[i]]++;
    }
    ll sum = 0;
    for (i = 0; i < k; i++) {
        sum += (modu[i]*(modu[i]-1))/2;
        sum %= MOD;
    }
    printf("%lld ", sum);
}
void p2(const vector<int> &cs, const int &n, const int &k) {
    vector<int> dp(n + 1, 0);
    vector<int> lp(k, -1);
    int i;
    lp[0] = 0;
    for (i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        int s = 0;
        if(lp[cs[i]] != -1) s=dp[lp[cs[i]]] + 1;
        if (s > dp[i]) dp[i] = s;
        lp[cs[i]] = i;
    }
    printf("%d\n", dp[n]);
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        int i;
        vector<int> arr(n+1, 0);
        for (i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
            arr[i] += arr[i - 1];
        }
        for (i = 1; i <= n; i++) arr[i] %= k;
        p1(arr, n,k);
        p2(arr, n, k);

    }
}