#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int	MAX_N	= 40000;
int			N, M, tot;
int			prime	[MAX_N];
int			flag	[MAX_N];

void Init()
{
	tot = 0;
	for(int i = 2; i < MAX_N; ++ i) 
		if (! flag[i]) {
			prime[tot ++] = i;
			for(int j = i + i; j < MAX_N; j += i) flag[j] = 1;
		}
}

int Euler(int x)
{
	int ans = x;
	for(int i = 0; i < tot && prime[i] * prime[i] <= x; ++ i)
		if (x % prime[i] == 0) {
			ans = ans / prime[i] * (prime[i] - 1);
			for( ; x % prime[i] == 0; x /= prime[i]);
		}
	if (x > 1) ans = ans / x * (x - 1);
	return ans;
}

void Solve()
{
	int ans = 0;
	scanf("%d%d", &N, &M);
	for(int i = 1; i * i <= N; ++ i)
		if (N % i == 0) {
			if (i >= M) ans += Euler(N / i);
			if (i * i != N && N / i >= M) ans += Euler(i);
		}
	printf("%d\n", ans);
}

int main()
{
	freopen("gcd.in", "r", stdin);
	freopen("gcd.out", "w", stdout);
	Init();
	int T; for(scanf("%d", &T); T --; ) Solve();
	return 0;
}