why????

#include <bits/stdc++.h>
const int N = 1e7 + 5;
int cnt = 0, p[2 * N];
bool is[10 * N];
signed main(){
	memset(is, 1, sizeof is);
	is[1] = 0;
	for(int i = 2; i <= 100000000; ++i){
		if(is[i]) p[++cnt] = i;
		for(int j = 1; j <= cnt && i * p[j] <= 100000000; ++j){
			is[i * p[j]] = 0;
			if(i % p[j] == 0) break;
		}
	}
	int T;
	scanf("%d", &T);
	while(T--){
		long long k;
		int P, Q, cc = 0;
		scanf("%lld%d%d", &k, &P, &Q);
		for(int i = 1; i <= cnt; ++i) 
			if(k % (1ll * p[i]) == 0ll){
				++cc;
				while(k % (1ll * p[i]) == 0ll) k /= (1ll * p[i]);
			}
			else if(k == 1ll) break;
		if(k != 1ll) ++cc;
		int ans = Q - P + 1;
		for(int i = 1; i <= cc; ++i)
			ans = (int)(1ll * ans * 2 % (1ll * 1000000007));
		printf("%d\n", ans);
	}
	return 0;
}