#include<bits/stdc++.h>
using namespace std;
#define Joyfine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
int _=1;
int n, m;
int a[1111],b[1111];
void solve(int ce){
    cin >> n >> m ;
    for(int i = 1, u, v; i <= m; i++){ 
        cin >> u >> v;
    }
    cout << (n + m)/ 2;
}
signed main(void)
{
    Joyfine;
    cin>>_;
    for(int i=1;i<=_;i++) solve(i);
}