ll@t;
rep(t){
	string@n;
	ll@m;
	ll a=0;
	for(char c:n){
		a=(a*10+(c-48))%(m*2);
	}
	a=a*(a+1)%(m*2);
	if(a&1){
		a+=m;
	}
	wt(a/2%m);
}