#include <bits/stdc++.h>
#define N 3005
#define int long long
using namespace std;

template <typename T>

void read(T &a)
{
	T x = 0,f = 1;
	register char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	a = x * f;
}

template <typename T>

void write(T x)
{
	if (x < 0) putchar('-'),x = -x;
	if (x < 10) return (void) putchar(x + '0');
	write(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>

void writeln(T x)
{
	write(x);
	putchar('\n');
}

template <typename T>

void writes(T x)
{
	write(x);
	putchar(' ');
}

template <typename T,typename... Args> 

void read(T &t,Args &... args)
{
	read(t);
	read(args...);
}

template <typename T,typename... Args>

void writes(T t,Args ... args)
{
	writes(t);
	writes(args...);
}

template <typename T,typename... Args>

void writeln(T t,Args ... args)
{
	writes(t);
	writes(args...);
	putchar('\n');
}

int gcd(int x,int y)
{
	if (!y) return x;
	else return gcd(y,x % y);
}

int clac(int n,int m,int k,int d)
{
	d = gcd(d,k);
	if (d == 1 || n <= k / d) return n;
	if ((long double) k / d / m <= (long double) (k - n) / d) return k / d;
	return clac(k / d - m / d * (k - n),m,k / d,d) + m / d * (k - n);
}

signed main()
{
	int t;
	read(t);
	while (t--)
	{
		int m,k;
		read(m,k);
		writeln(clac(k - 1,m,k,m) + 1);
	}
	return 0;
}