ll@T;rep(T){string@S;ll@M,N=0;rep(i,S.size())N=(N*10+S[i]-48)%(M*2);wt(N*(N+1)/2%M);}