Train2

using namespace std;
int a[200005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int i;
        long long ans = 0;
        int last = 0;
        multiset<int> s;
        for (i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            a[i] %= k;
            if (a[i] == last)
            {
                continue;
            }
            if (a[i] > last)
            {
                ans += a[i] - last;
                s.insert(a[i] - last);
                s.erase(s.begin());
            }
            else
            {
                ans += a[i] + k - last;
                s.insert(a[i] + k - last);
            }
            last = a[i];
        }
        multiset<int>::iterator ii;
        for (ii=s.begin();ii!=s.end();ii++)
        {
            ans -= (*ii);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

using namespace std;
int res[100005];
long long max_ll = 1234567890123456789ll;
#ifdef absi2011
#define __int128 long long
#endif
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        vector<pair<long long,long long> > v;
        int n,q;
        scanf("%d%d",&n,&q);
        int i;
        long long siz = 0;
        long long cnt = 0;
        v.push_back(make_pair(0ll,0ll));
        for (i=0;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (x == 1)
            {
                siz++;
                res[cnt++]=y;
            }
            else
            {
                if (siz >= max_ll)
                {
                    siz = max_ll;
                    continue;
                }
                v.push_back(make_pair(siz,cnt));
                if ((__int128)siz*(y+1) >= max_ll)
                {
                    siz = max_ll;
                }
                else
                {
                    siz = siz*(y+1);
                }
            }
        }
        v.push_back(make_pair(siz,cnt));
        for (i=0;i<q;i++)
        {
            long long k;
            scanf("%lld",&k);
            k--;
            int j;
            for (j=v.size()-1;j>=0;j--)
            {
                k %= v[j].first;
                if (k >= v[j].first - v[j].second + v[j-1].second)
                {
                    printf("%d ",res[k - (v[j].first - v[j].second)]);
                    break;
                }
            }
        }
        printf("\n"); 
    }
    return 0;
} 

using namespace std;
int a[200005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        long long now = 1;
        int j = 0;
        for (i=0;i<k;i++)
        {
            now += j;
            for (;j<n;j++)
            {
                if (now < a[j])
                {
                    break;
                }
                now ++;
            }
        }
        printf("%lld\n",now);
    }
    return 0;
} 

using namespace std;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("? 1 1\n");
        fflush(stdout);
        int dist1;
        scanf("%d",&dist1);
        int x = 1, y = 1;
        x += dist1;
        if (x > n)
        {
            y += (x-n);
            x = n;
        }
        printf("? %d %d\n",x,y);
        fflush(stdout);
        int dist2;
        scanf("%d",&dist2);
        if (dist2 % 2 == 0)
        {
            int ansx = x - dist2 / 2;
            int ansy = y + dist2 / 2;
            printf("? %d %d\n",ansx, ansy);
            fflush(stdout);
            int ans_dist;
            scanf("%d",&ans_dist);
            if (ans_dist == 0)
            {
                printf("! %d %d\n",ansx,ansy);
                fflush(stdout);
                continue;
            }
        }
        x = 1;
        y = 1;
        y += dist1;
        if (y > m)
        {
            x += (y-m);
            y = m;
        }
        printf("? %d %d\n",x,y);
        fflush(stdout);
        scanf("%d",&dist2);
        if (dist2 % 2 == 0)
        {
            int ansx = x + dist2 / 2;
            int ansy = y - dist2 / 2;
            printf("! %d %d\n",ansx, ansy);
            fflush(stdout);
        }
    }
    return 0;
}