/*
n = A % 9973, A = k * 9973 + n(k为整数)
A必能被B整除(A % B == 0)(k * 9973 + n) / B = ans
k = (ans * B - n) / 9973
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int main() {
int T;
scanf("%d", &T);
while (T -- ) {
int n, B;
scanf("%d%d", &n, &B);
int ans;
for (ans = 0; ans < 9973; ans ++ ) {
if ((1ll * ans * B - n) % 9973 == 0)
break;
}
printf("%d\n", ans);
}
return 0;
}