SPOJ ide 上一个极限数据最多只会跑 0.1s，按理来说 10s 已经足够了，但是 TLE 了。

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

const ll Maxn=1e5+7,Mod=1e9;
ll T,Np,a,b;
ll cntd,cntp;
pair<ll,ll>divs[Maxn];
ll prm[Maxn];
ll res,ans;

void Get(ll s,ll p,ll g,ll T){
	if(1){
		ll mu=g&1?-1:1;
		ll d=T/s;d=(__int128)d*b/Np%Mod;
		res=(res+mu*d%Mod)%Mod;
	}
	for(ll i=p;i<=cntp;i++) Get(s*prm[i],i+1,g+1,T);
}
void DFS(ll s,ll p){
	if(1){
		res=0;
		Get(1,1,0,s);
		ll a1=(a/s)%Mod;a1=a1*res%Mod;
		ans=(ans+a1)%Mod;
	}
	for(ll i=p;i<=cntd;i++){
		prm[++cntp]=divs[i].first;
		for(ll j=1,pk=divs[i].first;j<=divs[i].second;j++,pk*=divs[i].first) DFS(s*pk,i+1);
		--cntp;
	}
}

int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&Np,&a,&b);
		ll N=Np;ans=0;
		cntd=0;
		for(ll i=2;i<=1e5;i++){
			if(!(N%i)){
				ll cnt=0;
				while(!(N%i)) cnt++,N/=i;
				divs[++cntd]=make_pair(i,cnt);
			}
		}
		DFS(1,1);
		printf("%lld\n",ans%Mod);
	}
	return 0;
}
/*
2
1000000000000000000 100000000000 100000000000
14299762385778870 112999822 28773321122

*/