結果

問題 No.148 試験監督(3)
ユーザー uwiuwi
提出日時 2015-02-09 23:46:44
言語 Java21
(openjdk 21)
結果
AC  
実行時間 295 ms / 1,000 ms
コード長 18,878 bytes
コンパイル時間 2,176 ms
コンパイル使用メモリ 76,788 KB
実行使用メモリ 59,632 KB
最終ジャッジ日時 2023-09-05 21:30:18
合計ジャッジ時間 5,512 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 139 ms
55,664 KB
testcase_01 AC 150 ms
55,436 KB
testcase_02 AC 154 ms
55,764 KB
testcase_03 AC 158 ms
55,644 KB
testcase_04 AC 162 ms
55,812 KB
testcase_05 AC 160 ms
55,660 KB
testcase_06 AC 288 ms
56,844 KB
testcase_07 AC 295 ms
57,116 KB
testcase_08 AC 293 ms
57,824 KB
testcase_09 AC 275 ms
59,632 KB
testcase_10 AC 277 ms
59,500 KB
testcase_11 AC 120 ms
55,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
	
	static int dec(char[] a){return dec(a,0,a.length);}
	static int dec(char[] a,int l,int r){int ret=0;for(int i=r-1;i>=l;i--)ret=ret*93+ord(a[i]);return ret;}
	static int[] decs(char[] a){int[] ret=new int[a.length/5];for(int i=0,j=0;j<a.length;i++,j+=5)ret[i]=dec(a,j,j+5);return ret;}
	static int ord(char c){return c-(c<='!'?0:c<='['?1:2)-32;}
	static final int INTERVAL = 300000;
	static final int mod = 1000000007;
	
	static final String enigma = "!    6|'~%OEG(*1D}h*IN$r%qXY~&Q7rr)3cK'$k'<o(v1Hw+.?8( &QaL-t?(!#Aj%l%WbK;(;btk (vle$M%]w$g,8@'Q&,r#NT-6%a_&e)f~5H&,0&J$f4N? 7'i'%3Qx2 :_&m+qRZy#4bQz$nq`*.>Xw5,2ZA5+'E%[%d{e$#_lr**~h,t!#,@m*m2?0',AjW)B5:;!'T`+&q9,Z(LzeN+u}Ln-w(?6&5(!l'$}hJ $Gma$Q_It,L=L )3otX%CqGS(Y3i'.2WjJ)0Tmo+LQ2D,]<yC(X31))qcrU(QosC)9$zp'|]/B'F=ke)qh!c j3bI&Vt1a!f{-M*`e4/&kRa#-NP!;$*h@b*~8y(+^N~|-X^o (v#B4-T+rW+{NxU#a|oS+m+^n*A$4! &f:X)/'1p'5`D% O2<).oclD%5CNF (u60)#_wd%rjlb'Bh4k,I0:1!GZj;-q9']! TG0-PW{N(ka!9(h$yG [3=]' B7F+$](#!TWRb!'?jW-(Av-!Ibc/*@EtF I>Qj(>]C_%r9p#'/oR~&[Zrp,pp2[(i<w<*c1eI!6ae'$G~d=+4<4|$[=#=(]_af#l]Zi)$5G:(0h0d,}[KK)5xiW)_gfH,Qk|8'{c!7'%@WZ)V<F_#b9#2,w~)+!QY+A,H 'B-27Vp-N7e/(YtW;%5sMq PSq](E$u(%>mbO*eGY^*kt,*.ik;$()e]X l}/~'CqRt+gP<t(U1'< A8EW$F{{r%1Br=#^}tH!G~Q9#HI<)'>t>#*hS=/.=`/B'>YpE,G#Q  x3<{!o=7y$i9@D!Xypb,2zo_$o!9=#+He$*jjeV V~T3-)Qr5 uXP:!9ZM^'1IPo''4=j(sz;R)w])G&BfId*&^WC,O.FQ&{0[0 P+8A.'Ss%$=NVF*f ,c k7V; j7F{&pp]l(n`%c){_<l-D![l+hqbL+=m+}*~7J?.x^H$#EESi!uSDT&Y]R@$Qw;K%{Mrf'Imd[(|NFS-s?#C r0GE+.iaA,.oZM'['x]&<iNX .-.9$^oBq&B<+3!/O~##hkH( |M E)u=$.,u qh'^aW9'7wB)*a6Rk dB 3%>`NN)|@>0%km`/!eEk]-M+}o(A+tI)N#+a*9ZJ,)3}dm!rkA?.i}Y@%H#pS)>WU{%*u>|*qPgn :$H !?o~f$M}K%(;sb, fi,},1{-k%B$HS*Et$m+ebPF*1ABa*^v}:+x*[&!Y? M&eYFI-TA3D+I6&p 2n{`$0%(# 9@^S,*DkH-)?[%$cK'$..()<'A4*F*Q+t<,B3oi,!;=M,9duz(;M1e*X(wv)Q` 1+@{69$Oh*e*N[m:'?I!p&pap_$EI0/#4Yy$(NNG;%Np6e ^'0@$Z&X)+tgaB+(5kr(`yM-.o1iw$;h&]+YMs-'@#N,'X~5'%zdAx+6S^_-D $z)H5=D*QbK}'I/>`%MVZR&L,m6,gijz&h.XG*j'=H&/tTZ!.WHJ(uF^q-[%}/'$r1Z$8cRV'Pb%s,5FR$ 3HK++vfrD(w,h=$$eT[#U3#T'!f@s$2mw-(-&_d&4=.u&=M`~+Ox@}'#!9>%,r.q$YnSk+20oN!|mIT!m,Ki+;:=y%)# h (8S3(Xr$I,whoK&XBBJ*c7HZ$Ny't,1@;[,6 Y!'OiJ(*GrTh+QfUc)A*l=(5<eE#1>u[,>92+#. %,!#oHb-Y.fn)5$I[#^M2O-4uY/+9u0B&>J*~#?d.G vW+G pC8]!?Jh>!cw1s,<YiK-b<TO!`|b|*hpW@%K`Hs(V$=d*~a8i-C723.[Sqp&$^/0.>a$)+!Ux[ 0Vy$,`)>P!z/s=*!q'_'[t8A$3;wR 1QD#!o*KS&7!+)(b^ll m6Q6$b'Pv'*hxT+!2($&]ssN$FY:'!*VU<,&s$9#K%B8(~wb2 ~2R%& d(x##x:p#dm9U#H-*@#<ZSN+{ DE)8#Ep#fRm,%>!Z>*^q(g&<lI]*T'lF+I^lN(Y6k%$?yBN,?:CT+^nkJ$Ej]K(~#&p)[t<=,Oy00)(~u2)x[$C-{P-i%07m#&rkY|!PB}j*#;2S!`8@e+Uk&P-`fg.%Odxt#{OL) lPLe,M#0b'0Z^a(IM8`!wPmA(dS m(_45`*O,wV(#Gr $ndk3!VTX})fSP`,mR'/*^P)R+7&g'.@~y~- xgf+Q@O,*GK,G sN{/,r__p%_|nS*Rtf>#a+|5'/2[t!;^J8$h{;f,M 'W*PUV&&5mUQ+'kpp&<vK--s*&.'3E<j*'dz%$cJv_+f#u'&{YMt'|T{R*gZ])'~WIn&I9'P-9U.d!*Wl|&LOXN!&lB-#BUSI*`A+f+OQDO#:+`2 8;L '0=Hd(~A9I%l'NS ?r2(-k#<A$Ngw-!A&~e*qQ]9 fV1r*jPD +ii|n([ldI*BPU{$HL(w$v}'*!jh+5+-Z#2+Dv:~*v9^S#h,oi!9N[R,lD:a&g-5g+7,eV%t~M9$^J2F'l(G(# Dlc$xy]=&:D(W#9'iC#whn> {0tY+Yk{=#R>{N$5rmW,oP!-+fW{,#SKHs&&k;#)z)[r :qxP 8Tw}$d+Na(E/Q~*wD}K,B(?n$wC$2)mR/:!sC(=&(hDJ$o'F $,n2+!ab@9-n C(!K)YF!lCw}#;'U+'x^Hf$MY4? 5H}w!R2UC)^oWp'[mRO&O?W&,%W-%&>QwZ$l0>#![mke D[=G P'lu!LPV~ q1rx%Zq31+&T8,'$TgW+6m5d%O~&,)VRm=&Zf>=.YT76*&:2,.K;,_%Y5tS*Pqwl'bkS*&u&2{ '{0..Gv0w!}8`%)_=;i%A>zc,ebQe*n1/> 71T&*L|{b+eKiC$,l-o%!=x--*h++'x7]W*y&3A)'N8U,G(g:)$a3I('9m' YqMU,/#XB+{nsg'i/`s%Z*,B$8(+a'*<S6)1_Z'.f6V`%SO0G*f rL+?7f4#`tN@*& @}$clDq&88JN$;FZz)W{nz%vQBt 9Heq,*r7q+{PTu'/ukx+e,p_'B]tY-yT;3,(KD.-ix~W!w;s>(7n}o!>*7D!l F6(Vw_s mQ>a'q_]B qcU($s.ML'$> |$ISS9-cFam*w;8A*}}{N#2_e=#T@n/!nDZ$%t382)x)XV(eBF|!N#Z= $Dht#gri}*!$%g!8 VV,yZ}{)c4A'!89:j)r[^&*@.8-,m<wO#0 rn$zcZf)Vo0^$kS(g(+q}9!oe2y*f~ Z(@J>Z)Y&pM)!U8G!$wkd'$,OF*W}=_)q3?r-GES+!|Gkv-t:4^'(`zK' FN-#,EyK +eOk&gNh#.V81I!NX;[#bEL8$!t(`'c3!' nm*C#598q$H[ I)4drg!/%Cu+|L-0%sb2c->7s0)=aO0-25(*&i!X3)@#Lj$gc;7),r{C&@T&Y#X_=P Py[5-b w{(k*^X)4oHz-p_A?$Tr}R%aDqJ(Hq]@(R:UK&^*VD!L^m1%s[H<$54Kz,TQeQ$^g>J&C;{Q#k 8n-TMF@&Nk@$,eKE+&[&{r!RNL['x!)#.>aai+Y^0!)r:`I,0({a*(=*|'Itt'&VWmJ#_d4})A_$u+:p1^ y7R(*[D-m(reJ~'a6E^-CWsO&JzGZ%Nvu=%;3iS)7L%!)@{7c+0apB*D+Ae*sx6. vZ{V'N]ly!MDA-.%jN-,e?/|'_4W='o{dw+@b)>&6U[_+_s*[&';Y3+|3j7+|@)_*!z;d*+$}A+bRKd!bo$~)S9ha&#(`j-ZZ;3!Ameu*Mo7h(~P8T);GBB+JeLg#9!+<.R#eK*zNy|$QK.%+YSRo!]]H4'RaN|&=WN5 .x<<'=*QS!X1};(O/O&*DX~'$]k6j$Wv^!'{7ST!~XBU+{b}| >VzF)2gnJ(9w/i$$;w'&~fB$'9~`]&Nw|M-k&&?#j3T|,L'^#)aT#W-00c- 89Z_*cqc0,Oyn7$$<}<'RE`n!7nmI'_7#}*#>b#&CL;^$-LL:#@!-*&N)Q^)Mid&)gvsF-N|=R,G?55!T<Rf)0+ZC 'n}m$W[2n)0z}8)B;Wh-LYO8#)nxX&x4JE#PH+n!K06M+!'e?!y@'e$l1Fh%A@T?.9SPE [yse-w*7,$2U(7%& 3Q!_,WA '_dy-Xmpv(XaL8 I3!M+E e)-n)5G ?euT+*Yl|*r2|Y$!!v+)twv.+ON D)JYz5!lDnS)M@.Q%q^.L-)Iv3)Gd9J!<jgE*%7a[!<tjx(Y;?o 0.&p$_xz:$vxm0 <ESe,g){ -4jxA)YL,D!8Si>+dTUD-dF0( =.[w)6%+6&c(}I+`.Fd&;huj-[EjW'VEw6#!9.r#8/o-.U.o- 3(kF&3>o'#f^lX#bntR$:-Jb+Hn[8(kkwF'?kJC+0.ri %J&;%E4Vv%3+Sq(}m9C gOP )Qub^+ (*D'Nk9d$!hyd tWWa)u028!Mzd>((DbS!@6Vn,yJsU+?d_<#(|9b*V6;e%ai>+-q~Ba#:4z_,@O;s E RI'*5vL,C$nH-JPDr%q6-j't -V#pF.}-+}Gh)Q0m]'m?'Z-QBoF h;`-!SJ?&,~ X>)ycuE'OVKv#Mv @(?Gp%-I]Yv+-<]w,9^#+!oroZ'Om.'%LT7e,@vUE 7pQJ#Vr]%)Le< !>8p['U]*T D0|[&5;TU&?Hq!'=)jz*4=j+*O1+!-trx3(;>S8)!-ZH!0J!0(a0j1+>lng!T9<G,_Ly]#v~Ao';+x0)Ym3R,Zsaz'mHH.%7g(C.YGzN(T-]R+L[?4$<7Br)wJD *5DG.#~%fn *N7--aEsv$ZZ-k&N2pt-J tK-pf:p*6Rx?((*q*$X#T,)qNRB&_vvC$Zqkh([ouq!S9||'xGqC rfLC#;6>m#gn_R*nVp`)H|2_(:T9[$I't|&PM } yh(V%b(7B 9+/..vrv.,5jJM+D%sH+}`0O,~plK()q!n)WtP>%UoXx%Xr(0+ kpl)gY4)+M%[M+AOA/'2I@w(<O/v(r,Iv$?yQI)qkDo#6^]K%*;ci&0)cY PBd%,:*zk%9nZA-O2Id-ooxG {OAU Al-d#XQEc(:^]Z--TG},;@D4+x][x)^%A] i@@o+FwG~ JKOR#|/NC!d kh!(N:d'jA}l#{moc(WtTl-i|KV%~wbP%Tnu5%&p~F%r;3T$@$]2,4DB?,W%$l*ry9l(E.T8,RPED,DcA`-h;VV'Az%x-!FTe'[uY=&.q_g cF5@*@ZMI%/q+h-41oN$}_L0#yEO*%WB>r)Fb-5,D*mE%QUqJ's&,9 NH4[+HEy~$#w%P J;&c!>.lu!I~Be+Th4`&|l%C lTZ)#b$u&%8./^,|>R9%MU2K'CPhw&;R-3-#|^/,O`w+,,0tz!-7ZA)~+CV-X9G8&|`&f#-[hc+`ai},9*f:*QGuB$ `6-&I7uD,.8G- 5Iz_,Q3w> ?0z!'L-UM$WD^]!}JI]%WDJ5)B-@g%s8>o!uB^%!d{v: 1K#8)Rz{>'e!>#.RH(5$T)(6(J&WX*95vZ)^K-E)U#?C)?DRO#(8a9.7w'D+;~G4$=^GJ-6)~?.T6w )jCKS+<kA2-B09,-'DtX,FLNo vS#}'`BsN!,HGI-MvdI!i8qz*B!O7+txI=%).'Z$hsjB(I&.5.oLdv!+#Lc ?#nP$+1:S)9TO0+gH}5.(O!L&zDC_*~Ot;*s!W- 1'xI%1;ZQ%CR'+%-oa3,UX(a'L_l6-LM6n(LH?&+`]a*&b !v-gdn3#][t+*wfE?,D4:z&L(V@-$va5)ACUZ-'bNc-GtzU#'(c}*/M?h({sQ.!~kdy*g}rJ,O{NP!^VA0'r+]m*H$cQ!r(G}+ER#7*3oNA)NR'B,Hg?R-)6C> n(8a-b<22')o2L%CSGn(hWq>)+^}#)-YA2,vxm=*obql$Bc=r$1gmF-kcO{)#|R$*.^`E(oVQW&xx @)X^:L#l[4h's%w7)IX[-(xqw=+sn9{,IS6Q'[93W$se^E&Twd{&S(5U*(t!}#c2o<+/~Kj+s9ZI+h:hY-C)Ue&&xw`(^,0R)=1Wn(`O],&+R.x lSV?&v~uF%|D;?+m!0U$Hu(p)('>Z+m`oA#YQ,.'<t9R#4!}y+~?W$(M>b^'4yn5+$*g@)C<&})2<iN#bq;a*K6kn*[TJH&JV^l&w fW(nbFB$psVy%='d.,h6DO&g6`y,L5en*aem--j,o#,cmG{+RMA>,j9;c*T>fo&xB_Y,&UaG'{^$W(xJg|&?z&T!rBmY,P%nw(nJEQ+^rE, Vdr;$,-*L)OcMA!q7NY$iUEQ%e_t=+<=dk,v kF+rqjg)_J~R+ruD:%4Cb6)err|%[+#7'&D[O,?>.8!h-V((hlIK-(C|:%x*T3-q 9b!pnpZ$u3Kw+`Gn#.&<u,*Td36!Avg5$i[:9  %/>)vi[z'[E$7*V?5z+}8,~'Ys8j(K_?4,m$BN)o!L/ >X#X'nCO5(S,Hz#Mu_f#z2'Q%AbYy*4_Vh%{OY.'i!2b+mNBS!GUGF f5X8.X#YH!!vjt#[Hux*T>}h!;@2 $zbfL-Ga2G!E2.g,Ptyd!AJNq(YZ(+#2_CU';ht  1n!R#__JJ'AnhZ!tW!X*,U.9-5Y|y( z3a+_aCO QW/<(}F}#%ac>'&AVo_%[N.@-GFE[ jP@m+[Mu-.ajaH'aYy$.`#?r!A_&,&}t&_$#C=B!@iy;$=)(},UbJl Mwyo @r'_&]W/h&}L}q$Vl#%-}.Yn+@Z,;)m+fV#/Dta* ;=U*AcI4 PQA/%Y%:S(^x?w)@<Nr 7,$5%sf!$#Wd#P#Bu^d$Q;L6%MQdS&<{T9$X<aP =P!Z!Q%#B,?KKk+d@!1-$,Ne%)C Y$hPGR-]JTP-,@`I'HfL9 l.1m-t`:R+u[.@%8Rnx'~D~x'Fzlp)'C<.,pUFi)(0.g(MA[h$H-}%+qM{U#p9=t%/<A['aGD<%/Lil%?ZK3.rXfI!69CW'4$5<$!5}M*Q^';&#)&~&g~`v'ZerD+VXLP$^1t_$z1qs(FTPW(|J+R*nf]C!}+O3'iuYj#*<Q,%_,*2.%*5+!+eWf-/M&x,fli?)B!^Z#TKPD$+nj3.H$Mt#.c]n,HJrD$Lgqj&rptk%XX:^'|r$ ,JX2G)UP@'(SGN;, EXX+Zj*a,{NRm'5;Lb*0Am3.)6OO'A#n;. K=<#}-sm*>BQd)bF+H!KMFi #ynp'x8aL)pQp`!c,?X'z|`+'FPj'*Cm-X#a{ce-0R$;,7BWR(W@9`-PY4I#{hMW%(~e$ u!<l-jsu~ %_Tw(F2yG%CN*,!S7sD+,:T`)ad;r$mu-l#]JnW!;6nG)Hib8'-,sY+sLf$#a7y^*hYD?)5n[&%%fsZ-'-E8&sW!}$q:cL+vC&`,em/I,iJ?m#U+qp+,RRq*#KT] }e(y!P=$Q$iMz&'Dk#_-76!:.))Vr(*HR%$Ld@0.F>Q['dG0:'aT{+ /%&C(/a< +qt95.{:3e#^p5S!5X#-.o|Jx&n0i]*n^Tn#n%h$()%G(#n)S>,HDyh,yH*o-,_1N!CPV@ h(Ks YnSP*6-Dc+dj.%-Ev6X$Dskf,V,9P%,fZ/%iO*A+I0fZ-:<os&LHZR(z-fj&#0)?*`U02'S+9d-F2d=-FpiI!vqyA B,f[%t~I.'3n.F)Wxj8%,}Uv$7fs+&[lFr-QMaQ'rc_O%dFtd&xe)K#vQeU*>9U@'VMXq!Wq|@*;[O#*[?%#$kCKX,Y/C<.K#Vm$<1r1, NG;-M^5G-P!!T!Y`4<)=pCv*A=KQ-Bu$=$a:S~&B~[E-G=$6&N6q##N>uL!WI^E(M^$6&t%2B%^DpZ$$0CD w`gq#w'yP%@'4)(YY]V(FuE('3};k-Ov =(fS+j&K%0P(@Sv:%F(~[(g1#<-21C3+vxn!+PPr{+Ri3w'~{Z)#)jp(+&0<,,f6n^)Kj;K# u,/+WD|s*w}^S&^*~S %P3C*(MED&wyNe$aP{O *x::&wg_4%yQ7X#$J ^(i5C3(tS1_'4,|i+' xT-KIBa&jA4](gA:F)q<FJ#Bktb'Yf*A$a{Ku!),o=!zh:I-ZD{?)//K,,w!o6 Dc1'$--OE$hS0J!8K2G%/k$u'BD24-z8^y-#`5 '#L??!6Lc5%%4LJ!Jf}m-&COQ%C8S/%re9F'$PK/#Lt<r%.:uX,TaM$%CL/z(F#N<&{x%I*U!`],Xg2u'uc_F-BPPm#KYy1,dA-O)Kdnd*WYz^!JvU<&<R:=%#=+D'lGx,-`~f1-4?IM,k?~.)AsW(,:6ZK#:8f.'hp`D'{|w4)5j9J&~_4r))^@s!;+Dz*JT=m-rOln'#L,l*G:(q-n?M(,a[=#%XhZX-Rav%%BG^m%(J78#b'Z^ vcXP%m;5S,eLR?-'&qe+caF3,N<R/,_A6-+_1nC*Vp&R-mw.{*#Dj{(lgkd%=&Vf)zp}['|R79 /|y,.0kQ4&{ {f$&dLQ*[R[j&J9DG%V9Me'X/|l)xSNR(H0ai(.30q'*6R@!`o)!+-'+b*nOFK)5)l:-0>a5 UMc.)J3<^!tKN$&0jCW$(&<v+qkYe$%'l:$&MZy$Mt^C%_c>1.7:`C$J^W&,@}_@*C&kL'WFiB)}cFG&X~Y> V{=~+yQ%S(y.[=!UhXI! da7!3(VA$l@1i#`8tN%Kdq+'`bfg$UBk%)y:ns%FFyq)G:Vv$H=.6%Jd4Y!bANG*~R}r#4~am-rB>L)%^OB+j>tW-:b^7#y1?b->hXj(xg;))17k&$X'V6% ?HU,yv6{$Nz/N(&*Jc&12V5!4OQB!Ne<q$GxoJ 3DPu-''eF .$bP$~$hv)|_uM)kz?A ua,/&7h|j,(YwQ,)(d)(iTcP(X{Ym,n;(#$oL-C(ofyT(Bb6R&J74[ =S[A+Dm/f(8:Tz&M_#,!q_j!%N+3'&PpUx*__7'.Wwl9-q*Ow&g}hq S?&t,cmz0!8A4&.wMcN#~Wi1'upRG)}01X$kfz|*pU $#|A@H!}%7O#qAk>)oFTF'DI|t)WoCN,(Foz,N#4F#d|Dg!=wSE([LA]%vG;B!CF~7%PqYE(i9qV$`%[N&v`Pt %P8, c{EZ#0U>>.2iuO jROK 48(d,^B49-k6k (=3V)$fnEr)/e3;'Jno((!3?u!Kn3H!jhxy'g,EU$d#d^!U4.z&H!['$|);q&&]A5(|XI).BCFy(YSI!.~_-c-%'3O J{t7+Kd{!(;l3L$N/}v#x$D -~Ml$+99~T(858!*U##N&[!4g'@Y8s+|*p<$Vwy$#}U}h&!#sH#e~:<#H|-C(qZ*L+SA*p%r9#4#,!OU+{`b?'j$.^+z_zO*oA*B*u&yp#J3vz%S*.&*NWH .A?2='Y!]c$oB2<-6?P(+`eFp+;NBc'?B92&?jf+'bK:,#gBkF!}L_>-A.}Q,l#Jg({;Z3+JeuS+)**~'M#+2%D5+F+QW(P &(6V(CS6L#k)l2!8Pp:)^ 9^,x{Ua*dKQ;&q9Wd$o&Xk-IFxi `H|Y*:65B(C]67.}?xF&@o.>)0PKZ)g_hv,_PMr%ke#2'/NFD*+6k2%[;$w'YaHm+4J9G)<O_G%MXtL'J0=!!>rD9${`y@!*J+>(*m&2+?5m)'*f^2(Ox3V&2AF>*Vn8D+[5Xi+$b.',M]|p+v `D)*81> HJ+{->a_u)}jY>$%wEA$em=J+B?:3'!E;K$'tO--(n=r#L l!#q sb-S.,.(DtWF+O Ey(#E9 %0|ex,2$}@'~XYk'|gUA $%fI-y?C.!@YB`*%,mI)*!$Y&(mk8.7/xm,$+1m(.w C&CC1 -Q/PZ!(i}9+]u~$,QZ`i*Zre^,ktDX'PU17$R]{m,4r%L RtXF+@ *g-cFnA$};#[(QP&P!Rfi[*wt}%*55+B,!U&m#'L@A z{91,0`n?(GrWK-7$fg&U;1^#to/b,ugv0$U#*9+j<vf&C!Qh#X'#Q&P;3^)K a+%3Y>'+:q>g' I0)#k@ B*DzI:(aPz2#4TlM#,wG#)Y<dz!b9=|'XM~S%5w]O#3oV]#Ko u)O:tE-Dun|#U|' (Y*q($J&O{&Xz?9./h>+ SI7l$neyR*c(+`-_-ZU,ZII*'0UEN,;fXA.wih=,N%}%'G&bV,&]-o!.6(1'O49(+Om1$!_8( )yl`a*8yc* (aj>&>,zA-Ub<?*8&CU,*sdV,~#4=*>VP^*d`;8)'}(D)vwBp wU.| t+]y+ibJ=#%U+u!:6=H#X8_b&x(`&!Okr%#jQ.}(1gS9)Tq7~&>d?=!VlvI-)X 4)^YXh-`TY-*0)+u%fSaN&u[25'K<yH-O&gQ-3gpE$}$y?*;FN.*c.4|)q#.b%c(in*K)Ms'Y,c^ n}u9!f9- #?pzE$#oFi-l}~u#&Y=y-0G4((K uw&-W.> paGS(6@Cu)O)*j-5Mw5&a/nZ-0jgX!_smQ#,!af%&o;e(T,v}!i6<M'/Y,n)AvS>*.FHs$F+S(([,^#.p`Tg%yk^%#.B02%!z3O!n$iH#s7o=%YG6m !RJ,%UW+x*:f.P,?r8m#?X^_%V6O2)bjd#!rKRv-/&@m'wnb<.wk[U$>l[u(-jpS-(I^Q&$S#@*(.'h*Aobl)0.zP-8!I (B8Y|#]c@j'3f-l!9]:e(c5}.'m;fT'EB)*(ZgZP%,J**'$%+;*50u$*Xfa5 azD|,fRO]'H'$x%bub 'l5P%+pJ>R&xl,P$0}e..-A8c!<&2w!B&g],~IGk,..f?%+Fi`#s[H_-RN{W!-P[L'f[lY-bm?a$ilsd,0G+?$Q4&?*[1h=&Tnl6$U6>a,fz==,l`KT'O/WD,=9>6.8WYH'9xe?'*o)=*bn%f$S;W7,Hh$*(]@.=*wR^w%yUD$*D-UG 37@k(eA*k&z$75$Kn`*)i!bj+{|g  U_eI+pZ/w#P%)z#ne$N  :>F+0G6h)<Sh#%sHy0!j*?4*L)3{,z!%|)`jJ>%Ob%7-AKCn(Q.4b n#|6'Z!f6%@G)?*(u6M+AHA:#<:Id)R(L_(gHsd)oZ}J-$@f+!nOXj)XqkG%v:)T(*1Y!*pquh) Swa-ej/z*'KlR-hU,0+V~jw+zT)*%M`ck-`[C#.J&XV!>/_B,foJ;$bac, q*cY&7IwL%MoCa,;ih[(@| @$5SfL#4;i4'MvPM,)>Ql#)~#<+D3BI)I)t'(O^U?%,DKL-Z)ZU%S#Bo%d^s+%X.hp%uXwG*!i'p!G>;G*w~LJ-1?xA-8}*c 2_;>#fDZi,:TO,,fi_t-+<3()bS%<-LJO&,M,_6)i29t&q5/|#rj_.')sZ>(Sm*0(mbn0,0%9S+@%l.%D_Hs),h8`)Ax@E#}Gc$  ~Uc&=7sP! |'()x,Dy-+mAJ$5R?I$}Ec&& _L;,OFT>*K&7$(>7Y+*g]uO&mD>X'c@YA$H>{v-#&n{!7=;R!,mEe!vJeu%opM+.OA-y,^M'7*JWE%)v2x' 4p7I'L-5G#q7U&!m:~%(<.$!$3)kx(rjf2-pF$<&C;(/-Ub1~,mSx@+mP(.&9zF>,-;L:)!%f|#c3ld+(xrz$_yAu%QA&[&,|~c)0u~#&Lw+,*G0d)( *~K)0$@-!:BjP%zPp;+|2b6#7#FU&Pblh)^&II$7:Az+|H|B tPK@!-Y=v'/i=]!{>ST(s3hU+H.Ek,0[gZ-U%jc #Vg$,Q._z .V^<&J=;4$hwX .X@o1(J Yr*SD=B$.$u;!_};q 1+<4%<3AE!,h*p,H,0x)mjq|*XpT;.H!v@,.eR-)6$_L(g=/X!=,mu+wqa/,Ho'r,8IPl#Q^d+)T}3&#Nb4b&KKB:%p~t{&5|$|%e|kP#O~^6.b-BZ'>2Ef$ldi[!e`p%.[|_b%@W w)],t{ Z)Fo-f>FM-O1>c+uxbc QC*b(U2Gb*(EHS-J>Qn,BJJ;'2ID|!Kkyq(zN@6+FA}B.u1TZ*%%pX$c_wj%3L^$,tHJ,'6UC;-&BC_'sY<R*$YOK)a?&V!m8Wn-:#I}$OO!: N3h- v`D9'$QXq DYab'jM>N&<Zci$v,8},((ez!z[hg >T5J'4%!h!k!e!.T+m^&,R}z%_$D2(QV%',D%^)((jpj#q3^n c?81+nw K)MsP3-|Un9*xc3%(NIXq$7pI=%0K;s-O'Mn,<x73+-)L=$)%[d$1Nj?#$j7/-;M[K+aV+g*Q^YE,AWdk,Wh5q(k55i*)p~O$MYKH =4iF!Kte,)?)Ys))wP<.Wc$I(.+7.*f/(p+k'K)!QZB9!i<xm,(CD)&=#ZX!sfm.(N+*V-z{Yp#m.[z)2R[{$6K!4$b<M&&xHiO)2pr1!`l!d,3^SL(#xL2%>Vr'#;kJw wg]<)UL6L,}dy{+ fSC$79`=()%Vq Wpvy-1!M8#VMKh#.SuC'$bf% 86ua 0[m5 iSG,%~&<.-93d]%_G G UC j'R0~R&~%#Z+@7B#':zTw'hA|.)Km~(,ra6J!T4K6 aPJc*S&B-,)Q6.(m$-O j-;;'0L}L%=:y$,uvB*%/!^L'WQsG(GLlw'rF:r'+5?p+'0J*'6X4).d#?p)3O1S*bHT0*!xD/%Qm_U#e~-_*o#,9)ZZHy#PnH8(#=b{,aUr`'xcc`#t'U2!-GFH)okXN-m!c.*@b<$+v@j?&nS0&!6+a8*SRd. :Ba>+Ym4L(.8zU+f]D6'/2m&&ju~u('oQv#N=F>)-F8A'GF3*$8z!w&W H%$An47-'b;m&4589+wez-+v_$E# (1#'55`~&3kvV+4PDj*K'Ns*~tUH,B)~C(}7*r-1[29)bMqq+kM`]#1_SK _*F7(l/Rz(xBi~'kfK*(V.qh t1FW(3:(A,{4[Q!aPn= ;Lio =[qY*A9,h):]Hv#pl5=)aJ5f)}PiO$HpeL$WO4T(,zT/.C)u[(gV</(462N-$*[&#ZSRZ $(QP)*cg&$}d]4,9y;s&Lz?@)|[=k!)ZHW!LNQ4*DYs>#M0wM!Gl%K'l<%*./2<~%YqC^ o/@z),*Hj({NT^)x/)W'm17'(A?G2!s>DW%T4> !JPt$.Qr*]-^!~|,jt>Y&;@Fu-a2JU&xJdA-!'%o%(Mti#d[iv!+B,P)c.D~, HS@%avh{#zM9;(Buxe)HF||'JYu:+;n-P+*sRR'<v/?,bdN(,H+F{ xiBF-_a(>.a7E4.s-[< V{Dp$YaB'.#>:/(0UIm+=yEA)JK6T&d;qY$[w'b+m-_q%E{di$OVDA#6S.A.0;Bv Givp%&HLs'{N{',:mAg#pT2k,QbxN*QL?8 -i]w'4HLh'(`AW'remY#6GjF)?dRW*VtMM*E.7M#*I*s%n<U?,RA2K'D)TG-63ke*>o2/-tt!r'!uL!+OY]w-v2TY+HSB +Agx')dN]f!4a_X)V]Y[)^H2L+{i1a(S~l+(dxkg)mlC--3s$x%'$rY#,rz,,uk(&*/F;6%'e1$*ze3{+x5&9!ry3d,4qy:#RVf;!tV;B /yk_+}uVL)ppjx)3:lO(]W-4 }xbS)eOl{#>XsP(B|OP&T0~@ uBJ9+dr~/+#K;E(.1h<(1,yR$$FJ}': 2d$4kA$-=o?8'r,{',L>g]#>Ru0(#L$c*H3B/'MqU2.l '!,L0pP,wQd:#12.J'Q2;J(8Q>z >t1u+!@F!'AT(M&o-ky%A&hn(3c?K#ynp8-gc93-1;lc$5 ~()->4K&PV^o$'*t<+/H'`&(Ri (_~gT*zjv`$LEQA-,^e($cN9%.5lEt'!P$*,>)Fo sfQ]'N{| *Z~kJ#qKp},,!03(!rUU,NxEB%Bu!B!cXOQ#`yvD+OTf6(1^;X*Qwip$71Hd!;N8-,k*2r-aPYe)$W%M$NLhj$!?GV(3T81#Whv9,HOcq--?2q+amz).NBkl,l%dZ+%yWt+cED5!Xh%$%[x-Y$Jl#_,w/>f$]`Y+#XD6U(Xxy`!+<E|%aDJ-!;yB`#9YuQ)@k$U%DDuO)y9Ft%PBQ@(-KS;#j8#A%dI?i)LQXG('`vE!^%H.)KVd$+V2G(! BzW!D<oI-Sq|K)xo7X*I|@R!_:#c(}z4|) pBT+,N+| ]hhn-_@3w#pjoJ+T9{!.&o$3&}s>r#4T2_+x>u^'gu1~)8OY@!~$a0 |r5H'*B>3%<n!l-bA)d(DG]n(HMvW(Z;9I#Eaje!Dz^+-cuL@'jFC ,yV?)+*j){)q Gj!&z=W-8&g=#4~b&+/<i7),tIt+*?pa b3X+ )>Rd#FH,Z%H?pp#9#m<%h:Ii)Csrc*K]3@$X.xo,q*:?%aiX!*gAGH,7$f-%Iw1I!/e@'+8f?8'CM@8,*YDQ+'~ /.m~0!'mf7A){$ui)54oR![5w6')I$u!$`F},Ns;w!r6Fl#V=dh+C3:;%.QNY'tAxk)AS9/#Dgh6+`'|4$&2kX)6G7k,ko)L&?NZ^-y5?u+.+M=+w[Bn!aoXl&A6x/!|:BM)T[nY%2]6;!XvMS,SGBA#q.'z('@vf)fBE?,MY&+--zH+,7tpV$MJ<Y dkQ9.}+eh(Lpco,]O:d!iZLs)xeqL)QeAT,G%.''LJS**Ult$!%ZqV+*Loi#'|2#+Sici)|NA7).[V|$/q.n)E'uO*5HV_$|w*<).Vvn'!>!~-1DAi$i:~`+jOoU%M/((!=jQ#'D,,Z)8Q.V%ePtZ,DL{H)y~+^'tk~T)v4X/!OU&D)+K!v-oQTd #*[V+[;<{!6)fd#rTMf'SL@Z$RPqH$6g.]$IlOc%CR*M,dG}V)G~mF*Mwlv  UOl)6g_$ r*QD!Xx*>%'X`8!&I6A%ZcG++rMuY&#ISy$tPI='Is>:#' i!&|:x+&~,g'%zEMG%oC})(8lks'([@%&RHWE(UKF!+W[f,,k<ix$19H%'rdC)+dqG{+MmV$'*tkA%c;pH is=-#B[KA-S|z@-G9e0%X;2p!V'ca+.RB1#z02F-4 lO&K_#R%cfs(.e.I,)sL!P$@,+K&5-$8*ipH2*}{SL+mGJf(2hoI*9hAD${#^=!(~$z*r[Cj tM{8)Em|k,X>jC*~H+^$4yS]+.&Qi$Mt0d(P^-4!w(X$+$'cM-GpdV bDMJ)/Jd#)'N1e'ezK]%Fo>F)k/=m&DQ0c)55Bn%t-L1.pzC;#cC~W-pT+/+C_'Q,a!6b*jC$B&Z|s$!Ic3K#._&+!-,>w$cg`3.4?&e#r~$= Yw+e(/&&Z-J#1e*k(c)*{Eo]#NUaU,lE3'#!f;z-/]oJ*>$)p(Om;1 K|0:-(@Bq$+]RN&!XL>%d/wI'a,Mg,d-m#%V<%X$2g54+u~)@*?=Iq)|ty,*Dl%Z)dPo!%SJ2Y )Nr;,`'&M Ay'K*dF{b%#e[0(@8E+*5T0R,L.K* QIH: jhH|+*w?>&z!R&*3$@},aq^M)TkI<$&.'U)p_$q,gp:y+>Fn^#)bB],T)B])On]D%`O7r&mk s%~BuA)/Jkp -`S*&01s~,`K~'-cs98(Yzcw!!rY,-9Mrd't9nM$HM{g*Vs:&,hwSK M-bi,xG:i$Tr[:'2?*c %Uib jcLn(Wyk0$;K]*- ^G)*(=pz-Ic|t-sQ~Q(ty9K%zeXT+DcaR)j7+;-Ukwp#ZS/v*8/^*&H6hw-;jv1&@(eq)AR2W,y.wA*)7fl'n+IX+uF9Y+Ne&|-F!r%,}!Xi'5)P% `!}w&:Z<1%xU)--EPA%-xiMa--s3q%&5#)&,B<s$i]!9+Wduo 1jZd+CH2.)8/?B f@W5.us^_$`@KG+`CCt+Svo4%`X;q+uJ*9.+b;?%In%!.*IZ.+vsN*!2.#x,b[/@*GtD'*`'iW'GY2{#Ns}l+@a@d+(G8b'X$:&.$]%Q&bk;`%W,gR*BPCD+jEef+6,9?+~zE{&njih!7Pnn)s6}O'*O{% [eAg,h>[h+!qP>%ZYYr%nZXi';P6f%DH:N$A3El%}|a0 tbHY%+9h` o'/v#5G] (2B-<&Y<@.$S#{8 k$|u%9bAP#4c$Z!A.>K$(~9|&tF2! `K6'#,J#O#vk]J nr&I#~-lQ%Y5cl+~#In$Ew`p&g#8{%M |- ~A e)WOB;!H)?L a#t%,0H!U,CHx'%V`}:-92ni$=aw- iJOW(&01C%iXI-,Lkrx+HO/w+z4Xc&MS,P)g9xu#Ff)V+#8d3!v*;^-jP3Z&dY|W+d+r#)v7Ks'bv?z ?m-F!yx;O,e_rf#c)eH)^BL2'tubY+A=?& Y<) )$rZ-'splO&Us4g%K6?R*4DaV*O`K9,NDbv-I>M0%P|SJ!eJRN(i{KL)>qA<(YXlU+_@'9%X^>y)uMC0-s;tj,3{yU |%Np&Pw X+ztWN [Y{,!FE<H-#D5[-N g&(HX*H)qz>q'(qez&{DJO#D}B;% p'B-{m5P,^je{$1syz'TKn<#WTQ+'+hTx-uM|(*%eMp WUW')]e,r+H&q|)hZZ8-qCcM,U^5<$uR,4#ToZ4#%T2+ 5AbL'ei=m'U9RR!-YP0*od!d dju8)b>Ui#O e?)z1:,(28|:+*s5g&wd/_#y.EH+hs>X)%@ad J$6p-b}GT!^Aw[#igG1(Bmvw%dG=H){}iX+K*U0&L4q;.2p,E)$gw_(JrS!)TwZw-qLK#%|bj.+pfE|%K(3C+|,S9+@o,: `-B(&{agX+1k2#,uf@^-0Y;~%jm.}(+_4&+V0wR!)z/C-6?-X$#2rO,2QTy+}(1f(e>z^%}sTc(=Prc 1g3Z!VOBw(I?&Y!Z^q=!TC!v$.pc> 8dhh#Bemu&$vb?,]'ka*AH+ &UM5L+~kFB(C,rZ&48$&..5,H(fc-^-gUyp,<EXt#.O~j$:kl-!5oj1%&A>e,^ql,&Uo06+]x[!)Wa9{,U2BA'pwmI++W80%72S~ 3.hk&(HNM lP8e!hnV!.L}l8#Y{tq!l'ae%)#%[,K4bF+fH~t(9~ZD-";
	static int[] fs = decs(enigma.toCharArray());
	
	static void solve()
	{
		for(int T = ni();T >= 1;T--){
			char[] C = in.next().toCharArray();
			char[] P = in.next().toCharArray();
			if(P.length >= 11){
				out.println(0);
				continue;
			}
			long pl = Long.parseLong(new String(P));
			
			if(pl >= mod){
				out.println(0);
				continue;
			}
			
			long cl = 0;
			if(C.length >= 12){
				for(char x : C)cl = (cl*10+x-'0')%mod;
			}else{
				cl = Long.parseLong(new String(C));
				if(cl-(2*pl-1)+1 <= 0){
					out.println(0);
					continue;
				}
			}
			
			long sup = (cl-(pl-1))%mod;
			long inf = (cl-(2*pl-1))%mod;
			if(inf < 0)inf += mod;
			if(sup < 0)sup += mod;
			if(sup < inf){
				out.println(0);
				continue;
			}
			
			out.println(f((int)sup)*invl(f((int)inf), mod)%mod);
		}
	}
	
	public static long invl(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}
	
	static long f(int n)
	{
		long mul = fs[n/INTERVAL];
		int base = n/INTERVAL*INTERVAL;
		for(int i = base+1;i <= n;i++){
			mul = mul * i % mod;
		}
		return mul;
	}
	
	
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
0