#include<bits/stdc++.h>

#define Write freopen("out.txt","w",stdout)
#define Read freopen("in.txt","r",stdin)

#define si(a)           scanf("%d",&a)
#define sii(a,b)        scanf("%d %d",&a,&b)
#define siii(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sl(a)           scanf("%lld",&a)
#define sll(a,b)        scanf("%lld %lld",&a,&b)
#define slll(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)

#define lli long long
#define m_p make_pair
#define p_b push_back

#define lim 10000000000
#define mod 200
#define Max 100005
#define PI acos(-1.0)

///*** set bit and check bit**
//#define IsComp(n)  (arr[n>>6]&(1<<((n>>1)&31)))
//#define SetComp(n) arr[n>>6]|=(1<<((n>>1)&31))
using namespace std;

///* Direction Array *
//int dirx[]= {1,0,-1,0};
//int diry[]= {0,1,0,-1};

///** Translator Functions**
//int ToInt(string s){int r = 0;stringstream sin(s);sin >> r;return r;}
//double ToDouble(string s) { double r = 0; stringstream sin(s); sin >> r; return r; }
//string ToString(int n)  {  string s;    stringstream convert;convert << n;s = convert.str();return s;}

//priority_queue< pair<int,int> , vector< pair<int,int> >, greater< pair<int,int> > >pq;
//***My code goes from here**
int arr[202];
int dp[202][50][100];
int a,b,d,k;
int  fnc(lli idx,lli k,lli val)
{
    if(idx==a)
    {
        if(val==0&&k==0) return 1;
        else return 0;
    }
    if( dp[idx][k][val+30]!=-1 ) return dp[idx][k][val+30];
    int r=0,r1=0;
    r+=fnc( idx+1,k-1,(((val+arr[idx])%d)+d)%d );
    r1+=fnc( idx+1,k,val );

    return dp[idx][k][val+30]=r+r1;
}
int main()
{
    //Write;
    int tc;
    si(tc);
    for( int tt=1; tt<=tc; tt++ )
    {

        sii(a,b);
        for(int i=0; i<a; i++)
        {
            lli x;
            //sl(x);
            si(arr[i]);
        }
        printf("Case %d:\n",tt);
        while(b--)
        {
            memset(dp,-1,sizeof(dp));
            sii(d,k);

            printf("%d\n",fnc(0,k,0));
        }


    }


}