#include<bits/stdc++.h>
#define FIN freopen("./1010.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll T,n,d;
const double eps(1e-6);
struct team{
    string name;
    int p,t;
}te[maxn];
bool cmp(team t1,team t2){
    if(t1.p!=t2.p){
        return t1.p>t2.p;
    }else{
        return t1.t<t2.t;
    }
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(ll t=1;t<=T;t++){
        cin>>n>>d;
        for(ll i=1;i<=n;i++){
            cin>>te[i].name>>te[i].p>>te[i].t;
        }
        if(abs((n*0.1*d-0.5)-(ll)(n*0.1*d))<eps){
            sort(te+1,te+n+1,cmp);
            int pos=n*0.1*d+1;
            cout<<te[pos].name<<"\n";
        }else{
            cout<<"Quailty is very great\n";
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)

const int MAXN(1e6+7);
struct nd{
   ll a, b;
   bool operator<(const nd& ss) {
       return b==ss.b?a<ss.a:b<ss.b;
   }
}Nd[MAXN];
int T, n;
ll sa, sb;
ll aa, bb;
ll outt;
ll lasta;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> n;
        outt=sa=sb=0;
        per(i, 0, n) { cin >> Nd[i].a >> Nd[i].b; }
        sort(Nd, Nd+n);
        per(i, 0, n) {
            aa = Nd[i].a;
            bb = Nd[i].b;
            lasta = outt;
            ll tmpa, tmpb;
            tmpa = min(aa, sb); //喝之前的奶
            aa -= tmpa;
            sb -= tmpa;
            tmpb = min(bb, sa); //喝现在的奶
            bb -= tmpb;
            sa -= tmpb;
            outt+=tmpa+tmpb;    //喝完的
            sa += aa;
            sb += bb;
        }
        lasta = min(lasta, min(aa, bb));
        outt += lasta;

        cout << outt << '\n';
    }

    return 0;
}