#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=+;

long long mod=1e9+;

int T,m,sz;

struct X

{

    int x;

    long long y;

    bool operator<(const X&a)const

    {

        return x < a.x;

    }

    X(int a,long long b) {x=a,y=b;}

};

long long sum[maxn],cnt[maxn];

int v[maxn];

long long get(int now)

{

    long long res=;

    int l=,r=sz-;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(v[mid]>=now)

        {

            l=mid+;

            res=sum[mid];

        }

        else r=mid-;

    }

    return res;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        int n; scanf("%d%d",&n,&m);

        priority_queue<X>q;

        q.push(X(m,));

        for(int i=;i<=n;i++)

        {

            int x; scanf("%d",&x);

            while()

            {

                if(q.top().x<x) break;

                X head=q.top(); q.pop();

                q.push(X(x-, (head.x + ) / x*head.y));

                if ((head.x+)%x>=) q.push(X(head.x%x, head.y));

            }

        }

        sz=;

        v[sz]=q.top().x; cnt[sz]=q.top().y;

        q.pop(); sz++;

        while(!q.empty())

        {

            X head=q.top(); q.pop();

            if(head.x==v[sz-]) cnt[sz-]+=head.y;

            else

            {

                v[sz]=head.x;

                cnt[sz]=head.y;

                sz++;

            }

        }

        sum[]=cnt[];

        for(int i=;i<sz;i++) sum[i]=sum[i-]+cnt[i];

        int Q; scanf("%d",&Q);

        long long ans=;

        for(long long i=;i<=Q;i++)

        {

            int g; scanf("%d",&g);

            ans=(ans+i*get(g)%mod)%mod;

        }

        printf("%lld\n",ans%mod);

    }

    return ;

}