#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;
#define MAXN 131072
int type[MAXN];
int height[MAXN];
long long dp[MAXN];
int dQ[MAXN];


int main() {
//  freopen("in.txt", "r+t", stdin);
//  freopen("out.txt", "w+t", stdout);

    int testcase = 0 , cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase --)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &type[i], &height[i]);

        map<int, int> R;

        int L = 0;
        dp[0] = 0;

        multiset<long long> S;


        int head = 0, rear = -1;

        for (int i = 1; i <= n; i++) {

            int &y = R[type[i]];
            L = max (L, y);
            y = i;

            int first = head;
            while (head <= rear && dQ[head] <= L)
            {
                head ++;
                if(head > rear) continue;
                multiset<long long>::iterator it;
                it = S.find(dp[dQ[head - 1]] + height[dQ[head]]);
                if(it != S.end())
                    S.erase(it);
            }
            while (head <= rear && height[dQ[rear]] <= height[i])
            {
                if(rear - 1 >= head)
                {
                    multiset<long long>::iterator it;
                    it = S.find(dp[dQ[rear - 1]] + height[dQ[rear]]);
                    if(it != S.end())
                        S.erase(it);
                }
                rear --;
            }

            dQ[++ rear] = i;
            if(rear - 1 >=  head)
                S.insert(dp[dQ[rear - 1]] + height[dQ[rear]]);

            dp[i] = 1LL << 60;

            /*for (int j = head; j <= rear; j++) {
                if (j != head)
                    dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
                else
                    dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
            }*/

            if((int)S.size() > 0)
                dp[i] = min(dp[i] , *(S.begin()));
            if(head <= rear)
                dp[i] = min(dp[i] , dp[L] + height[dQ[head]]);
        }
        printf("Case %d: %lld\n", ++ cases, dp[n]);
    }
    return 0;
}