#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;

ll T,R,n,x,y,w,h,dp[maxn],sum[maxn];

int main(){
    scanf("%lld",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        scanf("%lld",&R);
        scanf("%lld",&n);
        while(n--){
            scanf("%lld%lld%lld%lld",&x,&y,&w,&h);
            for(ll i = x;i < x+w;i++){
                dp[i] += h;
            }
        }


        sum[0] = dp[0];
        for(ll i = 1;i <= R-1;i++){
            sum[i] = sum[i-1]+dp[i];
        }
        ll Sum = sum[R-1];
        ll i;
        for(i = 0;i <= R-2;i++){
            if(sum[i] >= (Sum+1)/2&&sum[i+1]-sum[i] != 0) break;
        }
        printf("%lld\n",i+1);
    }
    return 0;
}