int n, k, s = 0;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    s += x;
}
for (int ans = 0;; ans++) {
    int a = 2 * (s + ans * k);
    int b = (2 * k - 1) * (ans + n);

    if (a >= b) {
    	cout << ans;
    	return 0;
    }
}

for (int i = 0; i < n; i++) {
	cin >> k[i] >> l[i];
	a.push_back(make_pair(min(2 * k[i], l[i]) - min(k[i], l[i]), i));
}
sort(a.rbegin(), a.rend());

long long ans = 0;
for (int i = 0; i < f; i++) {
	int pos = a[i].second;
	ans += min(2 * k[pos], l[pos]);
}
for (int i = f; i < n; i++) {
	int pos = a[i].second;
	ans += min(k[pos], l[pos]);
}
cout << ans;

st[0] = 1;
for ( int j = 1; j < maxn; j++ )
	st[j] = ( 2 * st[j - 1] ) % base;
int n;
scanf ( "%d", &n );
for ( int j = 0; j < n; j++ )
	scanf ( "%d", &a[j] );
sort( a, a + n );
int ans = 0;
for ( int j = 1; j < n; j++ ) {
	int len = a[j] - a[j - 1];
	int cntL = j;
	int cntR = n - j;
	int add = ( 1LL * ( st[cntL] - 1 + base ) * ( st[cntR] - 1 + base ) ) % base;
	ans = ( 1LL * ans + 1LL * len * add ) % base;
}
printf ( "%d\n", ans );

int query(int x,int y){
    if(x==-1)return 0;
    cout<<1<<' '<<x<<' '<<y<<endl;
    string ret;
    cin>>ret;
    return ("TAK"==ret);
}

int get(int l,int r){
    if(l>r)return -1;

    while(l<r){
        int m=(l+r)/2;
        if(query(m,m+1)){
            r=m;
        }else l=m+1;
    }
    return l;
}

int main() {
    int n,k;
    cin>>n>>k;

    int x=get(1,n);
    int y=get(1,x-1);
    if(!query(y,x))y=get(x+1,n);
    cout<<2<<' '<<x<<' '<<y<<endl;

    return 0;
}

ll dp[32][2][2][2];
ll sum[32][2][2][2];

void add(ll &x,ll y){
    x+=y;
    if(x>=mod)x-=mod;
}

void sub(ll &x,ll y){
    x-=y;
    if(x<0)x+=mod;
}

ll mul(ll x,ll y){
    return x*y%mod;
}

ll pot[32];

ll solve(int x,int y,int z){
    if(x<0||y<0||z<0)return 0;
    memset(dp,0,sizeof dp);
    memset(sum,0,sizeof sum);
    vi A,B,C;
    rep(j,0,31){
        A.pb(x%2);x/=2;
        B.pb(y%2);y/=2;
        C.pb(z%2);z/=2;
    }
    reverse(all(A));
    reverse(all(B));
    reverse(all(C));
    dp[0][1][1][1]=1;
    sum[0][1][1][1]=0;
    rep(i,0,31){
        rep(a,0,2)rep(b,0,2)rep(c,0,2){
            rep(x,0,2)rep(y,0,2){
                int z=x^y;
                if(a==1&&A[i]==0&&x==1)continue;
                if(b==1&&B[i]==0&&y==1)continue;
                if(c==1&&C[i]==0&&z==1)continue;
                add(dp[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],dp[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],sum[i][a][b][c]);
                add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],mul(z<<(30-i),dp[i][a][b][c]));

            }
        }
    }
    ll res=0;
    rep(a,0,2)rep(b,0,2)rep(c,0,2){
        add(res,sum[31][a][b][c]);
        add(res,dp[31][a][b][c]);
    }
    return res;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int x,y,x2,y2,k;
        cin>>x>>y>>x2>>y2>>k;
        --x;--y;--x2;--y2;--k;
        ll res=0;
        add(res,solve(x2,y2,k));
        sub(res,solve(x2,y-1,k));
        sub(res,solve(x-1,y2,k));
        add(res,solve(x-1,y-1,k));
        cout<<res<<'\n';
    }
    return 0;
}