#define MD 998244353
Comb<Mint>c;
ll@t;
rep(t){
	ll@n--,@a;
	Mint z=0;
	ll e[168];
	REP[e](j,Divisor(a,e)){
		if(j+n&1){
			z+=c.C(n,j+n>>1);
		}
	}
	wt(z);
}