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