#include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <cmath>

 #include <map>

 using namespace std;

 template<class T> T gcd(T a, T b) { return b ? a : gcd(b, a % b);}

 typedef long long LL;

 void gcd(LL a, LL b, LL &d, LL &x, LL &y) {

     if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}

     else d = a, x = , y = ;

 }

 const LL MOD = ;

 const int N = ;

 LL multi(LL a, LL p) {

     LL ret = ;

     a %= MOD;

     while (p > ) {

         if (p & ) ret *= a, ret %= MOD;

         a *= a, a %= MOD, p >>= ;

     }

     return ret;

 }

 map<LL, int> id;

 vector<LL> rec[N];

 LL mincol;

 void bs(LL b, LL x, LL rt) {

     id.clear();

     for (int i = ; i <= rt; i++) {

         if (id.find(b) != id.end()) break;

         id[b] = i;

         b *= x, b %= MOD;

     }

 }

 LL gs(LL b, LL x, LL r) {

     LL cur = b;

     //for (int i = 0; i < 50; i++) {

         //if (cur == r) return mincol + i + 1;

         //cur *= x, cur %= MOD;

     //}

     int rt = (int) ceil(sqrt((double) MOD)) + ;

     bs(b, x, rt);

     LL st = multi(x, rt), p, q, d;

     cur = ;

     for (int i = ; i <= rt; i++) {

         gcd(cur, MOD, d, p, q);

         p %= MOD, p += MOD, p %= MOD, p *= r / d, p %= MOD;

         if (id.find(p) != id.end()) return (LL) i * rt + id[p] + mincol + ;

         cur *= st, cur %= MOD;

     }

     return -;

 }

 LL bf(LL b, LL x, LL r) {

     LL cur = b;

     for (int i = ; i < MOD; i++) {

         if (cur == r) return mincol + i + ;

         cur *= x, cur %= MOD;

     }

     return -;

 }

 int main() {

     //freopen("in", "r", stdin);

     LL n, k, b, r, x, y, bres;

     int T, cas = ;

     cin >> T;

     while (T-- && cin >> n >> k >> b >> r) {

         for (int i = ; i < N; i++) rec[i].clear();

         id.clear();

         mincol = ;

         for (int i = ; i < b; i++) {

             cin >> x >> y;

             if (id.find(y) == id.end()) id[y] = id.size() - ;

             rec[id[y]].push_back(x);

             mincol = max(mincol, x);

         }

         bres = ;

         for (int i = , sz = id.size(); i < sz; i++) {

             rec[i].push_back();

             rec[i].push_back(mincol + );

             sort(rec[i].begin(), rec[i].end());

             for (int j = , szj = rec[i].size(); j < szj; j++) {

                 if (rec[i][j] - rec[i][j - ] -  >= ) bres *= k * multi(k - , (LL) rec[i][j] - rec[i][j - ] - ) % MOD, bres %= MOD;

             }

         }

         LL tmp = k * multi(k - , mincol - );

         bres *= multi(tmp, n - id.size());

         bres %= MOD;

         cout << "Case " << cas++ << ": ";

         if (bres == r) { cout << mincol << endl; continue; }

         int cnt = ;

         for (int i = , sz = id.size(); i < sz; i++) {

             rec[i].pop_back();

             if (rec[i][rec[i].size() - ] == mincol) bres *= k, bres %= MOD, cnt++;

         }

         bres *= multi(k - , n - cnt);

         bres %= MOD;

         k = multi(k - , n);

         cout << gs(bres, k, r) << endl;

         //cout << bf(bres, k, r) << endl;

     }

     return ;

 }