#!/usr/bin/python import sys import bz2 import base64 data=bz2.decompress(base64.b85decode(""" LRx4!F+o`-Q&}1ZNX!5L0N?2=)b;_ 6iBa_kw=mARdh9k{s^U8%OCwiM`r2{cJ1HAEmu>XJ&HsR4mWB@m(#0;Z&rQB%~w|I6bypX_~T&YXUv< (WMFUugr~0hOpE+f+>>R$@$(R%Dr!wxi?SK~F7aH_lbYmW;~Dk %gIN$)#e4>%NY(-tJh53Yyw7rm2;rq>!x4X)TEa7_de=Xc{w>_pKOYrKrl@E2$O=O2VqO7Eac078jW1 30KuWFH#H-J==X7SMx>MK05p3@6JB4t4hqXO5ciB%F~66wB3_9?ByHxwvMqIQ)%&zi$;#ild-y-m|C- F#>+*O`J9&3w3%p#t&ybkTimrNa5^!H Bw&HVY$-YIW*%W!9my;nrzasRDb@m1FRJ#KXr)StF0#Hmxw@oMR6&`HeM$%bmPRMT3tF{LcYnPvqkLR(OaY^(&D+hj`_W>#RsRi=emkjzw?WVLEUzxx1}G)OYl8$ydyDv_0|8C 6EKn;6ofV=0-VYYb(jGhV-2#d)Zisy}__UFAad5oQ`;Y#7?G#f&sd7UoFos`>H7n_(*Up+A{8nUgi5A !)Q*MwTmEZ6soBHflC%Sy+{pn@N9lDBxSWkPKKN?=u@0*)Ki{nu*flCu+ nAX}%8i<2iYkB4-ugnS6h<{0{2`{L6_Ed4^%w1}NfS0wQe0Z*YZ!M^@eA{Sg@J4Yt0FCAv588J2bDvhD?17wTQeN%3R=cjsmza}TCoq)x-; Yz@c`5Vfx!xrwYHypJm3+zZqP{eI-o#h6wGFG|R2ih^rBRtnWthxC^KJEty}hfMDe2uvd}=*eLbYsTU ga^HM!{vIsm3j+4nBv0pe(gqKV0*RFi|dh-4xO5s?`otvVrTNUW&Y4oHYg)Ua5|Br)<&cZ|Hay6c!~%`lrYDMV6 ASv4Y?wej2?F-{B&NW}ukPa))*GEPd7CUSD;IGdVu=Q`Qc3kypo^lVraAz}j&6&}7;%heeGyMGNn9%xs%r^2KnOt5n6X%@o$Ev}DGMCAGBGM`;{0WLq;;D;i36N^)uvGe*O h>6xm8s5NVgvv)3>mS#*CvohOl;fEb&C|*fpFAB;4rFJg$<$^3?2Mj7e=V~!D)=26QKg?|m&Qt71-Q@ Id_9c{BFF4rl?8FX$Om&&{zW04r$5`EIWe;1-df4RUwPcGUKbKo?T9TaZxucpBrfD67)AI>!DhR+TM8 >&I9O#%M?i^NTQ6dT;Qk7+ox>GWsbW$wHDHvQ|kj(30!$g9cZ7AK8xUN0dvi6iSGV5F3;bij+#Kn?U) 3gl_k7*Be1W_&a42dRSz^Rh6$p+HWnVdLCEW%VIOJUnXyp4IDYmtmwh1By jV-j5lGdzB%}~rV+L)D^MWa}drmPV*Y8snLTMTNGO@@}WV^U%2}l?l^La`h;2^YJnl^%2kE^wV?Hu4w$fHhC5>uIzFTgj+bOr|n{>`kFS*&%qXv35-)xm4m_*vfnPP}*C 8EWajcWUj%S}r>?bul+ilSD~RD(4Jkh2PwT8u=bDQL#hKXJU}xytsQ%8hN9b}Xz?Q`RmJo=*tKl6>SY?=>iM5l43vPmLu=x%tq1(5U% |*(5%9C|le+HEn(PW5lBU#H`6H+7GO)nQ!uyCAMhE7A>iv`a5ZsWhG+CVq0oP(?j`mhBY;ki7nl^XqA NbI>l`=w_Aj)rfDgvG?tkbGJhX+>LL4nxr5lVOr*(XrqszB7HjJcopqW;q>6sOHR+RPnG$6bqA@L#N^ KC#WHOgyt4XV%>|^?+Eil x3BihGO?ARGrp&L`AiJ?kKF4Hs7GsDfPGM(dsRZj#@~IFV^kTn2aJMNWv6C#wY3=vy11)cXX4<_&!oU f%8x){TDVplqiA!8MOZDTs4aS1ZhMMa=*9<`wP%d U~+K*8aualH>I%+9WolpJZ`1M8@zQ^={c?9wLl&2JKPMvOdYTxO$OGH)a(pw5FMn#D_1PQw}qAA4Mi$ (I0d*`1t_?4D}XnS@x#Q9cpEa-eKytP|qpCg;PpHHxj@wbr8t@qE5n_7jO&OOynyAervm`k(-O5DG h?-4lhC4MtW^Qm^#TCrnIo63+FwBaq!Od4RY-@bVD&=6)GuBrq`}NR+*(c6(X;_P7vyOcCzg@n=vMqj hCARKx^2sMj!_VAvcxgyu;cX;RL|JdUd(KTVS|@EzjN)Fi2P8%$K@xzOG4405^JUz0OId 7u?%Z_OqKL%SmP({yC|Otx7EfNp$WkH0F}_Uou@MT^Nn%A5B}McHWm4H|?)jTNDs7hAe8miwCYH$yX( ZCMYO$7THm5OhjcU6>q&ZC@>YE^NSU0N2kT*hS+nvaZLXnCr;TPRm)C>sS%H L!aTIQ7iYE@X9;>~!^ymrp=Gws|(sqj5f3A=xC&Es`yN=XvJkirUQB(==`KT(#w2l_74=lagCWSlU`& -DD((|1gqHkrH{MezDN#_CmL;{M&ii!ga0}9OYXZQI@AM)0uR)TO8Kz*>DJX V(`RM1XR^uNc5$aCVn*hP&i9;XimDEqba}0kT5TL|vzD_XRx?wXUe*1!*XQXaWZAQ0WaX~D?QVohYa* 5UZNq6Vd3!G}by?|8BE!})l5;%-Vj>Jd*$z&Ch!KAjVZwTBmP?DSR5+A(cP8g^R(CjZEp07QDFquB65 ld`c`~-*TAp{U0n%LHvRhu+g*ojeDh_fWj(QHIo1Wl={YT34v3PRXw7)Z=( TUs#Ml~~1QD4Jt6w5?`knu1$MqRgs;84_B>NYSx~nWaj`O);h_Hbk3JOv=W!nJpS+gv~!*wtAs!wX>mS$FIZ!-Co#MWn)+n}uEb?DDkhrZ?%x93zZkwulMvkMxZGm)*ekr@QGmLitg6r`}zSc w7%nk;G>Xx6gQ%F&AkXsn2&HY|imVra@xOGz>tZE2Q5)-p_*tfXur)<|Y5GYYjdvkipJB<}sa*Wb>L) n+|Li&1(KL4*ETObbQteHfX6Ch~!y}cg#=79hS<%}Y4Uw~IQ%S2)WX_zm )Y>Z;(kr^VBMmjIV1`V#jHXs>)n=q=p_x{!nAK`qR&0vHRa-WwtzrfnSfq|gCA_-cRhg?AOv(JaC3Gi E6t)(_0~SEYB1{Qer;Uf0?Uw0zTJLiU%U)WzVFU7EQh4v(1Q;kmWu=05D7tAI2P9pT(d|d9H2UY!-Py 8=Rx535XQs7JF)VK;)u~yX4vt22%+Ce#tW!uDnB<(`LkW0I>{jm4I-c? 3u)MjLDqXv6DNVZt=3M(KCv?^dJox2EY}wGFHo{i1w#B1URNHGNNUS8(q|}T}Y>HVng>AISB5ABb+GS+IY9^+pp`zBP(*rcgOH(U JicvB$jb@mnl_83WhLMc_mS*iDWhu5&ku7an(v}ULn`5;^(%M+fW}227V75zAQks~O+9p8-vs)#JWg< &UVns1AF9NeV_7R{r6yFT+5Dw|=0(#4ZT#>!EtWl>8(q{dkzG%HDKNU`tTTPV(VHwih(lNG46UAek)XnrLL^nv}#eX!bXN7iX=t;r-Wk> hV>5A2?DS^lsNv%wWEVuXGyvN5n9Bk5-j4hJYl%pkutu(~3)A}A;Z&{7Sg{)}=b-`}=J>uG91!^%nY2(MMN2WI#d) {o))k{xm=h=ErQOa+c{lzET-nd79|E2HVB|vC 8g6dSts?BC9Il@QX}_l;h*FOTQmHPxiI=3`?hi(r9HVt`tPje&Xb(xwajR+*kSr}_1k>6EtR2cnk3HW 9ofaQ7PcfTv|3hnX{}l_GbX#8sM=j+mZO@xoh>=h?GCjUtS7#F^t)TLeKxK6e6@<-MzYD8O)#PQeQlm u`t)b%kCBg()pe-m1G2Ak&qmhKdk?d9w&*@7EG39ZTgz=anOMO2m0tDHjIUbSa_**TyHWQp*w18pQhB B_ZRD~FG22Qin_F6IWKCqTCQWVgbu5=S7~fVQ%$O6s^+5RmX_5lq?9O_$zx=!Y? @6>&>A+zf?;{mHGM2m+Q~80cQaf3Sg+Jz}edVs9?&SpLJ%)6eL{j4+B)d{4{6wM!dt7+lK>yoMG!x{Kc>+nkq&rz4a3C rqBnrqH_9P6F8OkyjiwGxDLI(^b;)cRFa0bPVF0&4`W9XwKJu$QIoL0$brn6VM(#5SNKTP>Hy%I4PHH ^wD=G~b?Qv7pGDrkt7D6Eru_Z;6C$9DHBR?9P9{dUq$p{LI;G-rONt)C=BA_&BT2`tLdYZ?6mmVIaUx n1vjCfbA9PSIJH=2zT@&g2=bzN-e7Ng~ZmoA=%9GSfmOkhVzClM+;^zUOSBMLzAzD%2#zV$rmbs47Uo tb~{fNTC#fu*tQa>jlGajQelh#YDbQ>h@ZD3a*MFoN)%9Z3fIXVk!f%l&M^Ym gcf+RI<85ATzgv=yIF={}xK6SUbN4esIvwl7I_qG0iK3~F;{AF0j$2iTcVv+hiX=q+Er{-m%1r-svfrPb{Az!p0exL@3&pHJu9uH&WmEyNwja63mF9#R5qoz1!%-UK EO#orbN~GvYSqGD;;JhcBX9_kjlc)WoDLTT2-(2C$o9k&ObFzVDlW#vaM~T+P16R%X7QA%8Oxpb2C5A >o=XrwVGW`kmmi;>oz9!!0D>&t8{x_*|ce5nnjpwR9^49uX%m$sw-{una(fj2+bOy=>MKmD-Ss1FV&hQH~v`pmmy!x>E {0a@~EmS@pSRT4cnm$DhDhYhMUxS-t45VGO}{wYxu?#~kzItoV=#76%@Y{T_p04)Jjt=G?{#?8 Y_!7OM=UyK#T!y+mTB5LRN7|EBAJnJ(P^gCbC+XUyOXk6k+G$wVr?R6EumzRvrB4NTU!&6%2F*@jT$Y PEXylNnwF+3Gc}y$8%CJgrybGDR=PTtvuL=Tly_$_C6Wq8t)Ux6$!qfB^tIa3SwOR7)Y_XCwIf4OX41 v;7k%B4rdqUXZM7D*Xs?o?+S*NHYh!+KT*9d>Pu;nhNi3T(&)n+l%wsRi>RY+_R%qHhvXYwC*i6mm*oj+?zABYDgAAnOUa3`P0$NIii@e8kb#8ncA6- cE`OQ37VG4L6%EtJp8w|!cIe;lcs59WzFt7dKuZ%HMI*zTDV(HH#LddiEh<%njYs1Y5eCVv`8j`+9f8I-yG o@(^)O1N>V=SjJy7~-neaE!geW>OwpEEq?VCVa@%s)df Z*-8LcO#Q06PLS(jQfNchy=%0$~jS&6JkNd>Gc)}rO38oO*=XEEBZcYQGAGE8-vaNj)DvsR&Bbt0vMEW0sMkwXrR>^xh`TwnNosXU$hur?hQsQ>v+rB#~IQB4J|5vc8U!oH@>F aY?(oKX)X_H5c4;eP?dvVzZyQ-r|eu0BsDKL0}?BeLffq4Aw<~B}oM&j9`8B0|oDoscI}7zUOp=#$CG MuI?W>vQi|&QB*2Zgyi^CzAmMXH{GWlF7vgE^FB4`iA&#Oe|||M0EPeA+9?gFY)dpO(pGC^s@7E2RAx qLnigYCBGxLcG_|OkRhSlP##yB{GSdu&t5p(UwY4#_MoSuvt1Bg~GDap_7Kn+KWU{u9gv~^W327$MS& 0<3wv9EGO`#^J#TlzwTUMIEtu-w~nKhX*B$mocYL;m#W@MF1EriV3wqcn?HECI*ZH&_<#;RtCtkT$pG _p%+M6D5`V#-2V+9s1}mMw^t5j0UIh_$v;OxmI wQDOwEt17nXcB4-B&%s`NNuB9VWn#sYGsK{jI|l9m8`Tt%Q8e#%SuZb6v-MbCRSp`TSaRa$~IQ4QnLd lnzUNfvqg~83}ZDdRTDIsAtJUd2{vhMCS@er%qC>bC1VsTQX)~UvQ?t15GJv$rkh%1rjtm^SlS{Ltx0 L369tK;sESQ#qb+JRqQyvMk+J<{L*=TkFq>AiW~sF-n)Xq4hq7IcZpksVQCc?G(W6@VeA`#1gp=i}If JsXqN}q=r+;(%9f#bKl=%778%T7{Ok%$Vg0*^?@o#b0mZ>S-XE&536An(w?7$P&$#x60N@wWI6N `toCAPYk7C7TIB#6hVSI>=qWs5uGKX*bIGy(;s3tH{|RB1GSrM5b+%8vUfaJ?po+EAH; G_vaN?^+aEO@~Jxt<0)0zW~IL8RVK9^&PZ*n!u`ie!)yC?H!aDT)mDBWZ>^2}^P@MvyR6!kkBiOIGQ^ um+P%}YZacZB%Xny2w)sl}1y2kXAfr6OLG1R2-Bjx*+&zeV)LU1|jgnJK7HrZ=OLDGcg{GSrq{(JPnu tvllvvR%<<^Z%+Q!MWnKVLLX0btu`PB%>i4XD=WO~Sa#+16mVElc#-um9CnX+vJAr*+p1oLH(^g2GK5HrF+iRtoalMYYuo*cAM`V`Qxs(W2OkS<|MKmffKb)|1wMcVv!S+6yFE?x8w&cYWIV j}>(+12eK&41lt*P=+aBps+a#oH_0mm4x*{O>dKH0T90jRMK!b)Fjc63W}-*Wy+p)X^U8}P}exxW=)9x^~oKsVP~AE>}*)d9Xn6Hc97bt%@w;{R9eMZrLy x$wO4DMx=(26Z2O0o+4kmJq}%9qmyXs=ip}!sld|sa6q6Tpu}KlG+O>at;ig2^yJ)5)+o0&$n@%}}8! BdGv6V9-W}|bLYB8?sieT#9GMgU5vF_bg?PhTeNi#{ZnydobGVMon8|Mq!m#kfh%eDU7$hNXcs7ZHrg 4=sKo21R!?*8-EM`N0-#j+jNLh5Eiz2`^NzLEEhi#K(Rln3AANidOQSsGB7N%? 8msxy*E2cPgHkbnEv@kjDg_vr(*kyl~Zyzic`oAt9&%{FF4WYsjr*0(Vhx@$^r(pAqpw9IWSi=TQAH? w7X_pfd8C8wRVwsgxm#}hPxSs?X+IXFd~7LSA2zP{ukJawE_kR4#CRTe1{v`$LNp1u3;yy;vuxTY9rW qIkSryNZR6^T$%W))%}i{DxI$%S7Q8|o7($Nw2rMGq-fihczTm~y=%K4*T|6a%Y36K8I-yzes~O+UB! 3a`uOLjQ7RsI8kxRqau=CdvDSaiuS7v~{Ow`{w6b@vF7ozl?|mNGicqXObM8CA6Gs*6w{htfOteCHs} =9%B#C1m^a`s6L@(z7$9U1XMy4QjzZN=X16{CwFGYt(rocN?3Z>-97Fz$#*vQT_g>ywiCyk;OP(%GAt z$BX?tqrtPhO~*(tyAC9UNF2h9Am86VTW87r>EpYH@Ot{d{70;n7AjFI2#q-{UPem!?{J$^X$ &UDBLs|iW&a*VQ#Z^Eo_g8}m)CxnSxNR#MiPLZneUv)BMO%R$s-ck=9Bw9Mo92r6PH;X UX5c>HF>9g#QivpY}-u{)k1iPmHP9RG)Gc%vqw?NXGPWwrDH~G 0YW&0JIII3-d~E*8zcVw(cQRW^nj}U*%nJdBt9~CChWf)G24JCCvr6bMQ28wXBlHR1f*}koZ#A9%LjCjKjWXN%Cb@cU$J;^LyP&_%xe9)+`!jS gOXTnz!Eew%&?lgSX!;{p0pF-=VFgCANNZ-e*OumXjrcMw(Se)~n`hwu$Vk)|gIZ%~6^@X*z0+GCwf( Pe?P?l%8N7N%JKdo)HsUAu0;uZ~B;1ORrdp%+MRkqSM1Mj_SV%HP2$*|SK7yq xb=o&yn+nAPlqg)}7a>FaF>F=d|375^YWYu7(7Y$AC!`(~Je561rFlHl5&fQIE@^XZ*jrfBYifMs`}3 #Lo^5_?Xf2CgYK^Xi1yHP&7K~^3OvMb!#U?wvzkna*TL<-yPED#!6%yQH*3#Q4l5S3$It9Hq?|k!GdT x)u%-i~4t*ZqO&#nw4lQL2XDoREVQ2nQm_dvr}O0yGd=1Pyvu=>-rOc>k0JgZ{tSDKc@+ILQwvzTL!Y ZO@U9EXPj*6#N`k_Xw4HJ&BJOM^noYPAqycB_9=Ss@#nj~eC!9~MeXd 3a;#znJgn>{=dtce7`CB;s#zrH>p>iKcGYSVvsmwlC xWUwk>jZd)u!{EhYn40i=-0Qd=xp3?%%lqAcfx3^f$8+QPC)QhdO`lQzQ0E#B@i*v~YQC__qLMo1Vhi $8t9{c4&Yxag_rOq13gyDQi4=J@_&j^ZN-em0!XZTI)$I&n0KB|}X6!Fz@-E)J(K+@96ECBLIU)j(&{C9v9oQ1UVmVkA#7{O>$SoF W`xhvm@NT45xD!|B3*zc`~_)vH8-=CT$h`z^@^9Sr#Z_QG^Ur)6!$uET$kgr~PCxY=$CF&kZ_o}0lVf *>cxB1^{AG)dgGamlGl7E_iRDQemFVugUi{tlxKGa{7m)Q>z_3t6-UPqMmJx>>_n%hTn-YoZxT3E?h| M7PuQ-uiupmdDD """.replace("\n",""))) def g(n): period = 149459 head = 105351 return data[n if n