rt

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
auto i = cin.rdbuf(), o = cout.rdbuf();
char tmp, st[9], cnt;

uint t, n, q, x, y, d, ans;

int main()
{
    while ((tmp = i->sbumpc()) ^ 10) t = (t << 1) + (t << 3) + (tmp ^ 48);

    while (t--)
    {
        n = q = 0;
        while ((tmp = i->sbumpc()) ^ 32) n = (n << 1) + (n << 3) + (tmp ^ 48);
        while ((tmp = i->sbumpc()) ^ 10) q = (q << 1) + (q << 3) + (tmp ^ 48);

        while (q--)
        {
            x = y = 0;
            while ((tmp = i->sbumpc()) ^ 32) x = (x << 1) + (x << 3) + (tmp ^ 48);
            while ((tmp = i->sbumpc()) ^ 10)
            {
                if (!~tmp) break;
                y = (y << 1) + (y << 3) + (tmp ^ 48);
            }

            d = gcd(x, y), ans = x + y - (d << 1);
            while (ans) st[cnt++] = ans % 10 ^ 48, ans /= 10;
            while (cnt--) o->sputc(st[cnt]);
            o->sputc(10), cnt = 0;
        }
    }

    return 0;
}