#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
#define f0(a) memset(a, 0, sizeof(a))
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#ifdef WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif
const int maxn = (int)1e6;
const int inf = (int)2e9;

int type[maxn], h[maxn], last[maxn], st[maxn], wh[maxn], dp[maxn];
int T[maxn * 2];
int n, stn;


void update(int v, int x) {
    v += n;
    T[v] = x;
    while (v > 1) {
        v >>= 1;
        T[v] = min(T[v + v], T[v + v + 1]);
    }
}

int findMax(int l, int r) {
    l += n; r += n;
    int res = inf;
    while (l <= r) {
        if (l & 1) res = min(res, T[l]);
        if (!(r & 1)) res = min(res, T[r]);
        l = (l + 1) >> 1; r = (r - 1) >> 1;
    }
    return res;
}


void Solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &type[i], &h[i]);

    for (int i = 1; i <= n + n + 10; ++i)
        T[i] = inf;

    int le = 1;
    stn = 0;
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        if (last[type[i]] && le < last[type[i]])
            le = last[type[i]];

        while (stn > 0 && h[st[stn - 1]] < h[i]) {
            update(wh[st[stn - 1]], inf);
            --stn;
        }

        dp[i] = findMax(le - 1, i - 1);
        int pos = upper_bound(st, st + stn, le) - st;

        wh[stn] = st[stn - 1];
        st[stn++] = i;
        update(wh[stn - 1], dp[wh[stn - 1]] + h[i]);
        last[type[i]] = i;
    }

    for (int i = 1; i <= n; ++i)
        last[type[i]] = 0;
}

int main() {
    #ifdef LOCAL
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    int tests;
    scanf("%d", &tests);
    for (int test = 1; test <= tests; ++test) {
        printf("Case %d: ", test);
        Solve();
    }
    return 0;
}