#include <cstdio>
#include <cctype>

struct istream{
    
    template <typename T>
    istream &operator>>(T &x){
        
        x = 0;
        char c = getchar_unlocked();
        
        while (!isdigit(c)) c = getchar_unlocked();
        while (isdigit(c)) x = x * 10 + c - '0',c = getchar_unlocked();
        
        return *this;
    }
    
}cin;

struct ostream{
    
    ostream &operator<<(char c){
        
        putchar_unlocked(c);
        
        return *this;
    }
    
    template <typename T>
    ostream &operator<<(T x){
        
        if (x > 9) *this << x / 10;
        putchar_unlocked(x % 10 + '0');
        
        return *this;
    }
    
}cout;

template <typename T>
T gcd(T a,T b){
    
    if (a == b) return a;
    if (a < b) return gcd(b - a,a);
    
    return gcd(a - b,b);
}

int main(){
    
    int T,n,q,x,y;
    
    cin >> T;
    while (T--){
        
        cin >> n >> q;
        while (q--){
            
            cin >> x >> y;
            cout << x + y - 2 * gcd(x,y) << '\n';
            
        }
        
    }
    
    return 0;
}

效率竟然还更辗转相除法差不多。