#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

vector<PII> get(int m)
{
    vector<PII> res;
    for (int i = 2; i * i <= m; i++) {
        if (m % i == 0) {
            res.push_back(PII(i, 0));
            while (m % i == 0) {
                m /= i;
                res.back().second++;
            }
        }
    }
    if (m > 1) res.push_back(PII(m, 1));
    return res;
}

LL POW(LL a, LL b, LL MOD)
{
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

LL exgcd(LL a,LL b,LL &x,LL &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x;
    x = y;
    y = t - (a / b) * y;
    return res;
}


inline LL mod(LL x, LL y) {
    LL res = x % y;
    if (res < 0) res += y;
    return res;
}

LL solve(int n, LL m[], LL c[]) {
    for (int i=0; i<n; i++)
        if (c[i] >= m[i])
            return -1;
    LL ans = c[0], LCM = m[0], x, y, g, mm;
    for (int i = 1; i < n; i++) {
        g = exgcd(LCM, m[i], x, y);
        if ((c[i] - ans) % g) return -1;
        ans = mod( ans + LCM * mod( (c[i] - ans) / g * x, m[i]/g ), LCM / g * m[i]);
        LCM = LCM / g * m[i];
    }
    return mod(ans,LCM);
}


int opt[100010];
int val[100010];
LL f[100];
LL g[100];
LL d[100];
LL C[100];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        printf("Case #%d:\n", cas);
        scanf("%d%d", &n, &m);
        vector<PII> Q = get(m);
        int tot = Q.size();
        for (int i = 0; i < tot; i++) {
            f[i] = 1;
            for (int j = 0; j < Q[i].second; j++) f[i] *= Q[i].first;
            //cout << Q[i].first << ' ' << Q[i].second << ' ' << f[i] << endl;
        }
        for (int i = 0; i < tot; i++) g[i] = 1;
        for (int i = 0; i < tot; i++) d[i] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", opt + i, val + i);
            if (opt[i] == 1) {
                for (int j = 0; j < tot; j++) {
                    int now = val[i];
                    int cnt = 0;
                    while (now % Q[j].first == 0) {
                        now /= Q[j].first;
                        cnt++;
                    }
                    g[j] = g[j] * now % f[j];
                    d[j] += cnt;
                }
            }
            if (opt[i] == 2) {
                for (int j = 0; j < tot; j++) {
                    int now = val[val[i]];
                    int cnt = 0;
                    while (now % Q[j].first == 0) {
                        now /= Q[j].first;
                        cnt++;
                    }
                    LL X, Y;
                    exgcd(now, f[j], X, Y);
                    X = (X + f[j]) % f[j];
                    g[j] = g[j] * X % f[j];
                    d[j] -= cnt;
                }
            }
            

            for (int j = 0; j < tot; j++) {
                C[j] = g[j] * POW(Q[j].first, d[j], f[j]) % f[j];
                //printf("%d %lld %lld\n", Q[j].first, g[j], d[j]);
            }
            LL ans = solve(tot, f, C);
            printf("%lld\n", ans);
            //////
        }
    }
    return 0;
}
