#!/usr/bin/python import sys import lzma import base64 data=lzma.decompress(base64.b85decode(""" T>t<80ssI1|NsC0{{R30QTOk%DXtfh7)nauiKAdM1bqW;dvNDJjbx(@I+D#unGIpQ~nEL=B^N|M(qK$4O? lTs+)`R~}{1Jet|6G99d~83!MMUYlo^pXT0xAI8qE7LpVrb5hbEEW%mf?iVsvqlwg9@L1;cvFiR@p>h yoZv2$fSOYG7mkKtGQd1z^6DJUe+39gJ@yeyi%QFcm-CVXOFGa~cIX`H)dg-u)(>|k6z?IpW3>R{v(v BF{kExwb+yO*$Wp8 KXodl2=kQ-+|!DgDJN*iEU|Np6zY1to#jViGeFSX-n4M_4sa?OWB94w9IhXHoMQn$Jelc16!g8(Oj6N 6yi>l|I&2ai_zROsgP3?K(rW>1tRG{Hfg;r@@mgY2cZt)^zSbZIV4`RLPeuP2GVi*^^)Zidp^@QrAVz -dp0=5++kxNH121taSsIo5Abgz?i`WqUwbSd6f=E3dbDp@2T?uW}pxu$U^F*}DBlC&)oS~j=m>Doem+ MBkvW06P1`Ari32lT-XWNZrt(VZb1K6K*l75pc7jR;wf{n{}n*x6zKC9YLj0Hr?9S;$pa*~AP{j=)b`dBQ&1Mpo#^`_opyI4`BaBie`t2mU& NL`jy?ccTc);;Ab<`y>f6%BCwIUE;^B|!X%=DyY^wl_Y&O?)IugQQ~eG%*d7L9dh7Y5O< H952cVT)w6qx$-0otNC*0j7K*tj-F58gRh~RnnNdLXtN(cS%Ctthcqu~l6jbAvDwqpId03S3UO8j-G6 GLs*Mrnm0G?0{I`r4z|QUJ+6jS0sDkm`hjz!wUUh-$4akZvNQnN!2O|LIvefZ{qN(6S*N-$6({g7tPp F>VYVl8XCvu)~#k=3V`Y!RF8J3olpi=t0z`2S>A$gX`C7g87TE7r?9lAkSucGN ~D`0Hdl8}FA^QC!>9R|j5ULOSb=`+*~g3x5oU0G*0re;H^!<9Q(FYt?6p*TT;}H`BliRQxMZ m_d@{dWE6<_zC)PGPMA6k)7oJ{57!F};6=!HzH}QuR(f;v)I|ghh`>ZkeOQ+9%*{rFXHz 2IO8pZCiN13fkop8W!V1funv{W6*TO3E{ZnO1+WTH?vO8^!Yt=iLEi!f_bh)R={%OwIqsD3D_A= gIfZBbmi7eHMSfB4D(;$}2ypy>-YRZn>K6W1#*umdFtMWOciMuv6x+&S(oQ8RUQcB@~&|!>$DliOf`E T2{A(( &|d=bGH-mbrDNFKrA6+yNag3m3qx+`G(nrsgCwp(odN>WOP2&kw8e^a!GotiPW05kRr(Z5*|hz(-8+x VuW1#(ebgW3N-rlMMCV0<40XM`RVx8{fv&uux%y{_T!iA2Ti9Wb7GrawMTZ2=e0J!0OcRUIo=_uysHl yC}Xqv&FV6RvD4lie=3n6oT0+6xBql`lV#E=PBNGt;dr%KT9Pk*hqWAJ$`SvGvYT)z |)BcPfhO|Yl93uta6@;n#giLo=aDm1DqK#?@r4!IPMEIF#PEP-JTGxXb&3j>~dEI-}V|#TG3@e3C`vsR}Sc(NL#Rk%kjwe3lE2(K=IHFq0$suHmyN}ozj;=J8;YrIYN++IKi +6h;6KznVqtrLfEVT2@X=sR{4yN@BGX1$A5rkY!$`gk!>b(af1Q~fJby=!kG6BDG)07XN+lU4osZ%34|LbPb`k+pkwzX1 ~6aXH+-pokkGhMdZQ(qG{tAc-;a9I{#=HZ<;pW_%XzI04u`@1oef?@eJoO^@oG5XWUs7brRb{j5NCV^ G4QEqO7j6Alpn{t)KXy4LA2p3!AhTZQWRj0|#ZuBEU#IAj}h6buAI68sFjI%83r}d&3=b#aSjK?sg1+7zC?qgIA+F8V3903)dWm0Ln~#6215StIq@kwd-@}5(l=zanHr| Qe)=7BS`lT74y+BMpwk~ST{LBs;Tce%whSJTXDnuX(9JDW)GhESPQ3|Oyr5$590-$f(Wp85a-d2yQ`t )OfdrK$s5z?NpS#M@SY_kwt@s@<0cL#FJ8~NOkMv0^rDb?Gl~9e52XIyg*105UbuHL_h+L*gk24CNY( ?}+FGL<)tZ)Rp?s}*#c29NR%>(z32Q15S23y`+)l9G`3US;RX5yS*MPN^}ksPG_DdYMpmf1Ol;pI1!BCFOwnv-7NbAfBP{Gmqa>6y_z(SCF-1rkT!>wJ#&b9?i+-pb^ I&mN9=z!F}|{hu&?ZJ&LartdM3kqf^hFJt_gC4N?qyXC9mSXZya`iLJUag{jFT~>&?U0j+pu@EKM^!X D2RIC^4`k}wPhDC$t3j#?x=&{XiMO+Sr<-gKW25r2*EHBbfl8>1^N SD?C;k#~bX7TC}0+^?YRchA+tc!{F;3U0Wr_?7AV);O~c`i&HlLrqgtsw7bR1W)9$=m@PRsBE2ql+Oh QxXQ?&d>%w(1-c7ZMA?V>%=SRSK%$yUSGDnmCupg4G5MQh$O!mbpA@=>5&A&MCG q1r%w7T$VQ#|+fg{V%s;y`hoz44Ia~I9ueAowVIynO)m&nL+YcBM7c)n6#uN?%r}mI&CA}a5E|1D9#Q 6;BNg_5^raI6?mx!>F3W*hZ(Mi9VWw?Y0yp$Pp+z^9aBLJU0wcwj&X;JPH;H6oPi6B(e_!5I3HvYhx< n!5pV}!fk=Jt-~|K9mmGBPTZ<&TkzvJITm#w;nG+W?nA&)A^%5STQWD4F3{8m5z^w$%qlxf49iUYAZ<`0aAgu;C)7p %E*j3f{HeogR$*a>AI%BqGHb^yQ<10klF``c4jr|O;rc1tieCcrVP?KBN2z{gqbM)?Y220w=;M@i5Pb yDOa4(s>zd?sXC$8(c14f7`43&y>E2N=*e+K=w@_=Hyr{3g2gCQYLds*=k{m^by0@!oI@CH=(`@7&u &j%scc4ACtOOij^-;m~xHp1bTs@;mrp~z&1%&pXy8q^_LN6TVOTb%1VEEaWuCfl}Ct)_#gh^MPvhF2) 6JC_t!1J!HVWv6qx1(w>xEKL*I*A34B!9>`kk~^z}%uU~7mq&T77QX8IWQOp?zpXBw$Ah}_@a~i-6}T 99oV@UC+>xC|(FJ)m>m1J4#U2M00s=XJ11oxxBQu(?kL!(c)UXyM1UzpKo50vB_taTU7Fl~a>Edi-Y0 LTL9hvI`$4lj2`uPiLT>9GO7;|2gDBIA1Z~~$o@8U-cHW5o_4p4hic!w|4TzH4PjnXj%usjX7R)MZcT 4BG|4ihvz`5KOnl2}$`yi~Z|a=-Hu?cuhDf!DaIIJ%I5v#^%<%RBMQ%2Njmdz_G}5YV`69z)G|j{O~% TRt1r^nKIyONp|lxbste>oXgggeVUS(sqS3MZ!3=B-ll)eoW3~iXTT;z%s2C34#?V9+Pb66J7v}r2~x FWYrSTnOA?H0~$45+Ihv~rO#~t^v*(-I!iRTzmspiqO4}aeSB<0pdI>z&G_mhuj2aWng=1?CR%BVyMf W$aKxeoBZ7YU@X>-o*jv}+R8@+K4bBz^^b7H0(b=J{_R=m@q7@6m8NrOTPvdoc3#6bI+sRiOh b{(wQZ@Irkhp*73OF`n~W87HZ!!71UslPjzSs``sxn2Ctc3Qr^~_!nEBt4DDMER#|b1uVv*g+7k}-un MtWd~5S$$f2iGu`x*N5Xhrz6t=5}MnY3ef-PuW!AkF=yC(QNR@-2benY>F6L69&VaCLB4D@W@v4n&BK8f<@SA72H*w=( rPF_MLHiWWWXKnpTKs|cek=sqxZluAk>bVU`_d(UGpa%;CIW?*%T{%oz^2>!F7Fk$vC5aTRu-C=lH+t 6WyCj~6JEn<9h@x++4z|)lHjEPVx!LaVZqL#+t~#+68z&D9^`V`(_(G2JBqc=HuKqR=H=Bv8BgYI7zv~XFDrN_z?$#o m~CD-U*8cFWLw&k`>zsING_sBSvvYnRta}%yfU0I7w&*`>A9e {Y(Ch3EwNpOO=#g(IFvEcJ&-Fi>I=RSl#P; 9^EbcW*!UVshk*jzI>z)>~7}3Q)zUChKKNWGclo~V}?^zsNK-+kS=nI%K$K~D(F!v7`?xa=nClIKxe#&U6Ig+{J0t~|d FPbZ)2uR5{(4MQao(BeazsJF%3m=7kH64Qr&=H~LsP7YaVkZOfi|{t2VIwXh*6^F!+~L-cEkXdGL1M*<27;0qycGkDDaYJb;H{a>QQM OTND)GV12%K>cEv9m)>JO$iL>+2&oIDYC1wePkPcaLr?2JczV~(1eLG514Pp9ErorI?IN{Qb-o{Uw&G=KVmuuUdxuJ&f)vHwgJAE3zziG-z0>;{#1gBQe}o3OLW#k3>w%T{dm%m&^QdFsc5I`Mum9xBol- C}qVz2Hg+ay9fzTSy4BM?3;#ps||C%#1i8d2rgieE5f}&6Oa|R;^Ys-lJ b6-!+rOqV@P;+PQPDlKLlJ1sXaZYPq`zhB2;#M$sz#c)tvkK7g{EaGMeKb@eW~D=GEs%#lGM2jOqzt_ YGO0k#_e~)(L~YXoKZl5o>cN=d9`$;sK2LKs)C=7`9Z~s02eQ$+(v~gxti}j9>0vvH;|^86+g8)E-KL m|&)Vy~=g`K!i}3r>ahBrYb2s=2;(a=j^2Fl}S-trOlsiNHFR&DGtU~70&_(5-*U5bJ*xN)tay Y6Q$t5S(;m!XsrdSCi-nQu0Jp7`?-v-(kHVPY9+`bkKQ!XH|V%eJH3^2U+5+D~*TlrR-8z^`q?a9R;u 4BJT$rLPSp3&+cj3^MDA=6IB>rzT*&+jKS2Nxb*KyC8OMZ*dEEM3I-^*C@P+OCcb({a1W!~??GJdwT1 aV4xLrj3z5s?+CHu7sIpR4}hfHdmw)jC}AXQdUYRvwW9R0K|tqfE|`T2WDSP|{SXgrMdMLJfa |r4s=6pSqx{*Zx>=qW>{(;&B#y}}vrO)OS-tgAl&X4_)V{}-__V!7MO9gO5FS%`1Q1 n=Du%7s733$B9FF3yyz*g~ckYdY>wE*{>8+R4uR1velU5UQ`;HU)dSZAdwVpwCxV+6{61`Sdc1!h8p% +(EnSHoCXk%B<%bGHvyw*CTq*kANx;b7G4?5F*lI8%6Cv@#c7X;P9oGN&B8NR-7tp|{Yy=V6rF!`?Mg ZXL(_AVFp2FwB@LGj3m|A7!zWT8Ayhd{5jKl(T`SS_shbFQ;YQLLuo`LFaIgn?yuO)i%|B)Dv%nyE52 WBrSb3%-sKZ7Ma1D-R|rq(44^@(Vu^QNI0Dwl8!gVHu {h%fkk}=Jmt+sF%M2HjZWjvlsuhrL%$gAGtCSgH!~cZ3UV9oKfv;AmM^tZ*=aQs;5(D#M(k!(zT KujiPQoR7P5)7`!%-{+pL$kr9JF&TH=_){k$IK)$Y7#^XU -qxiY5fqG*YJSMjJg$jYCm*=U1ghsYz3i?8W%Yen5XL;q*pRIZ3)FyS}U7|<@*=|cdd7OLn(xZF&;Kb `T4C{Bt$87oKUpK4>m3w8lFHyAPNF*UzlhWurFi)orK$<B=oK%V+`%o!!r0m meA%j}$-|7!~ayF7k|ygw%RVdlWDoz@a3XLG`c2`8rGs~k6c;RZhD2quHre+x6VPMO7BZCBV67%YPKb jqnUr7e3sW!goyf_rVlk(TiG!R8QvE?YCS+u$0z;1DP8KSjs2 n-0@2-Dk~bl!+jeDQe875cmzl0SYUyb#{zH72b0nw&sc~MgKa?Qqy&sGT)M$vua^b~DH3 pQu^v|Mw{(#TnRA~FUeS^=8xr$F%SPiiTstKnjKBPXM|a{F+~6u*8w;f1Io*kT~jN;C6NCi}6II_niu1F+pREN5DL9%?T2*%*V@u37di q6_{LZ+&zH~jH>^h9SNh)@x?avuJG+G9d$!uw;op6<-YBY7?y~qF^(@|B6FE?Cxh=~-x6I^A@Bc~QrI%$zhFC&w;cE;@n7M=uJ!-fRD!>2va%x % """.replace("\n",""))) def g(n): period = 149459 head = 105351 return data[n if n