#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 1e6 + 5;

int n, s, m, k;
int p[N], d[N];
ii a[N];
ll dp[N];
map < int, int > M;

ll tree[N << 2], lazy[N << 2];

void doit(int x, ll v) {
  lazy[x] += v;
  tree[x] += v;
}

void push(int x) {
  doit(x + x, lazy[x]);
  doit(x + x + 1, lazy[x]);
  lazy[x] = 0;
}

void init(int x, int l, int r) {
  lazy[x] = 0;
  tree[x] = 1e18;
  if(l == r)
    return;
  int m = (l + r) >> 1;
  init(x + x, l, m);
  init(x + x + 1, m + 1, r);
}

void update(int x, int l, int r, int x1, ll d) {
  if(x1 <= l and r <= x1) {
    tree[x] = d;
    return;
  }
  push(x);
  int m = (l + r) >> 1;
  if(x1 <= m)
    update(x + x, l, m, x1, d);
  else
    update(x + x + 1, m + 1, r, x1, d);
  tree[x] = min(tree[x + x], tree[x + x + 1]);
}

void update(int x, int l, int r, int x1, int x2, ll d) {
  if(x2 < l or r < x1)
    return;
  if(x1 <= l and r <= x2) {
    doit(x, d);
    return;
  }
  push(x);
  int m = (l + r) >> 1;
  update(x + x, l, m, x1, x2, d);
  update(x + x + 1, m + 1, r, x1, x2, d);
  tree[x] = min(tree[x + x], tree[x + x + 1]);
}

ll query(int x, int l, int r, int x1, int x2) {
  if(x1 <= l and r <= x2)
    return tree[x];
  int m = (l + r) >> 1;
  push(x);
  if(x1 <= m) {
    if(x2 > m)
      return min(query(x + x, l, m, x1, x2), query(x + x + 1, m + 1, r, x1, x2));
    return query(x + x, l, m, x1, x2);
  }
  return query(x + x + 1, m + 1, r, x1, x2);
}

void solve() {
  M.clear();
  scanf("%d %d %d %d", &n, &s, &m, &k);
  n = 0;
  for(int i = 1; i <= k; i++) {
    int l, a1, x, y, z;
    scanf("%d %d %d %d %d", &l, &a1, &x, &y, &z);
    p[++n] = a1;
    for(int it = 0; it < l - 1; it++) {
      p[n + 1] = ((ll) p[n] * x + y) % z + 1;
      n++;
    }
  }
  n = 0;
  for(int i = 1; i <= k; i++) {
    int l, a1, x, y, z;
    scanf("%d %d %d %d %d", &l, &a1, &x, &y, &z);
    d[++n] = a1;
    for(int it = 0; it < l - 1; it++) {
      d[n + 1] = ((ll) d[n] * x + y) % z + 1;
      n++;
    }
  }
  for(int i = 1; i <= n; i++) {
    M[p[i]] = max(M[p[i]], d[i]);
  }
  n = 0;
  for(auto x : M)
    a[++n] = {x.first, x.second};
  dp[n + 1] = 0;
  init(1, 1, n);
  update(1, 1, n, n, 0);
  vector < ii > vs;
  vs.push_back({n + 1, 1e9 + 333});
  for(int i = n; i >= 1; i--) {
    dp[i] = 1e18;
    // int mx = 0;
    // for(int j = i; j <= n; j++) {
    //   if(a[j].first - a[i].first > 2 * m)
    //     break;
    //   mx = max(mx, a[j].second);
    //   dp[i] = min(dp[i], dp[j + 1] + mx);
    // }
    while(vs.back().second <= a[i].second) {
      int L = vs.back().first;
      int R = vs[vs.size() - 2].first - 1;
      update(1, 1, n, L, R, -vs.back().second);
      vs.pop_back();
    }
    update(1, 1, n, i, vs.back().first - 1, a[i].second);
    vs.push_back({i, a[i].second});
    int j = lower_bound(a + 1, a + n + 1, ii(a[i].first + m + m + 1, 0)) - a - 1;
    dp[i] = query(1, 1, n, i, j);
    dp[i] += s;
    if(i > 1)
      update(1, 1, n, i - 1, dp[i]);
  }
  printf("%lld\n", dp[1]);
}

int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  int tt;
  scanf("%d", &tt);
  for(int t = 1; t <= tt; t++) {
    printf("Case #%d: ", t);
    solve();
  }
  return 0;
}