#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
                 std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;
using namespace __gnu_cxx;
//*/
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
ll t, a, m, ans, g;
ll gcd(ll x, ll y){
	//cerr << x << " " << y << "\n";
	if(!y)
		return (x == 1);
	if((!(x & 1ll)) && (!(y & 1ll)))
		return 0;
	if(!(x & 1ll))
		x >>= 1;
	if(!(y & 1ll))
		y >>= 1;
	if(x < y)
		swap(x, y);
	return gcd(y, x - y);
}
void solve1(){
	for(ll i = a ; i < a + m ; i++){
		if(i % g != 0)
			continue;
		ans += (gcd(i / g, m / g));
	}
	printf("%lld\n", ans);
}
int main()
{
	scanf("%lld", &t);
	while(t--){
		scanf("%lld%lld", &a, &m);
		g = __gcd(a, m);
		ans = 0;
		if(m <= 100000){
			solve1();
		}
		else{
			;
		}
	}
	return 0;
}