hdu1576

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int t;
int n, b;

void gcd(int p, int q, int &x, int &y){
	if(q == 0){
		x = 1, y = 0;
		return ;
	}
	gcd(q, p % q, y, x);
	y -= p / q * x;
	return ;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	while(t--){
		scanf("%d %d", &n, &b);
		int x, y;
		gcd(b, 9973, x, y);
		x = (x % 9973 + 9973) % 9973;
		printf("%d\n", x * n % 9973);
	}

	return 0;
}
/**/