#include<bits/stdc++.h>
using namespace std;
int dp[(1<<17)-1][20],N,INF=2*pow(10,7),height[17],shrink[17];
int solve(int mask, int indeks)
{
if (mask==((1<<N)-1))
return 0;
if (dp[mask][indeks]!=-1)
return dp[mask][indeks];
int ans=-INF,cnt=0;
for (int i=0;i<N;i++)
{
int temp1=mask&(1<<i);
if (temp1==0) //belum diambil
{
int temp=mask|(1<<i);
if (height[i]-(shrink[i]*indeks)>=0)
cnt=height[i]-(shrink[i]*indeks);
else
cnt=0;
ans=max(ans,solve(temp,indeks+1)+cnt);
}
}
return dp[mask][indeks]=ans;
}
int main()
{
ios_base::sync_with_stdio(false);
int TC,i;
cin>>TC;
while (TC--)
{
cin>>N;
for (i=0;i<N;i++)
cin>>height[i]>>shrink[i];
memset(dp,-1,sizeof(dp));
cout<<solve(0,0)<<"\n";
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IGRwWygxPDwxNyktMV1bMjBdLE4sSU5GPTIqcG93KDEwLDcpLGhlaWdodFsxN10sc2hyaW5rWzE3XTsKCmludCBzb2x2ZShpbnQgbWFzaywgaW50IGluZGVrcykKewoJaWYgKG1hc2s9PSgoMTw8TiktMSkpCgkJcmV0dXJuIDA7CglpZiAoZHBbbWFza11baW5kZWtzXSE9LTEpCgkJcmV0dXJuIGRwW21hc2tdW2luZGVrc107CgkJCglpbnQgYW5zPS1JTkYsY250PTA7Cglmb3IgKGludCBpPTA7aTxOO2krKykKCXsKCQlpbnQgdGVtcDE9bWFzayYoMTw8aSk7CgkJaWYgKHRlbXAxPT0wKQkvL2JlbHVtIGRpYW1iaWwKCQl7CgkJCWludCB0ZW1wPW1hc2t8KDE8PGkpOwoJCQlpZiAoaGVpZ2h0W2ldLShzaHJpbmtbaV0qaW5kZWtzKT49MCkKCQkJCWNudD1oZWlnaHRbaV0tKHNocmlua1tpXSppbmRla3MpOwoJCQllbHNlCgkJCQljbnQ9MDsKCQkJCQoJCQlhbnM9bWF4KGFucyxzb2x2ZSh0ZW1wLGluZGVrcysxKStjbnQpOwoJCX0KCX0KcmV0dXJuIGRwW21hc2tdW2luZGVrc109YW5zOwp9CgppbnQgbWFpbigpCnsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJaW50IFRDLGk7CgljaW4+PlRDOwoJCgl3aGlsZSAoVEMtLSkKCXsKCQljaW4+Pk47CgkJZm9yIChpPTA7aTxOO2krKykKCQkJY2luPj5oZWlnaHRbaV0+PnNocmlua1tpXTsKCQkJCgkJbWVtc2V0KGRwLC0xLHNpemVvZihkcCkpOwoJCWNvdXQ8PHNvbHZlKDAsMCk8PCJcbiI7Cgl9CnJldHVybiAwOwp9