#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1e5+300;
const LL INF = 1000000000000;
typedef long long  LL;
typedef unsigned long long ULL;
int a[30], p[30];
int choice[maxn];
LL dp[maxn][30];
int cal(int x){
    int ret = 0;
    while(x){
        if(x&1)
            ret++;
        x = x>>1;
    }
    return ret;
}
int main(){
    int T, n, cas = 0;
    scanf("%d",&T);
    //预处理出来数字i二进制中有多少个1，因为在有定位置的数时，需要保证前面有那么多个1
    for(int i = 0; i <= (1<<16); i++){
        choice[i] = cal(i);
    }
    while(T--){
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%d%d",&a[i],&p[i]);
        }
        for(int i = 0; i <= (1<<n); i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = -INF;
            }
        }
        a[n] = 0;   //只是为了初始化
        dp[0][n] = 0;   //只是为了初始化
        for(int i = 0; i < (1<<n); i++){
            for(int j = 0; j <= n; j++){
                if(dp[i][j]!= -INF){
                    for(int k = 0; k < n; k++){
                        if((i&(1<<k)) == 0&&(p[k] == -1 || p[k] == choice[i])){
                            dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k],dp[i][j] + a[j]*a[k]);
                        }
                    }
                }
            }
        }
        LL ans = -INF;
        for(int i = 0; i < n; i++){
            ans = max(ans, dp[(1<<n)-1][i]);
        }
        printf("Case #%d:\n",++cas);
        printf("%lld\n",ans);
    }
    return 0;
}