#include <bits/stdc++.h>
#include <map>
#include <algorithm> 
#include <vector> 
#include <string.h> 
#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <chrono> 
#include <thread> 
#include <iomanip>
#include <typeinfo>

//define
#define trav(i,v)   for(auto i: v)
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define all(v)  v.begin(), v.end()

//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const long long MOD = 1000000007;
const long long inf = 1e18;
 
using namespace std;

int root_n;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

ll power(ll x, ll n)
{
    ll res=1;
    while(n>0){
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}

void always_ignore_function_name()
{
    int n, x;
    vi dp(10001);
    dp[1]=0;
dp[2]=0;
dp[3]=0;
dp[4]=0;
dp[5]=0;
dp[6]=1;
dp[7]=0;
dp[8]=0;
dp[9]=0;
dp[10]=0;
dp[11]=3;
dp[12]=0;
dp[13]=0;
dp[14]=0;
dp[15]=0;
dp[16]=0;
dp[17]=3;
dp[18]=3;
dp[19]=0;
dp[20]=0;
dp[21]=0;
dp[22]=0;
dp[23]=0;
dp[24]=1;
dp[25]=6;
dp[26]=0;
dp[27]=3;
dp[28]=0;
dp[29]=0;
dp[30]=0;
dp[31]=0;
dp[32]=0;
dp[33]=3;
dp[34]=3;
dp[35]=6;
dp[36]=0;
dp[37]=0;
dp[38]=3;
dp[39]=0;
dp[40]=0;
dp[41]=0;
dp[42]=0;
dp[43]=3;
dp[44]=3;
dp[45]=6;
dp[46]=0;
dp[47]=6;
dp[48]=0;
dp[49]=0;
dp[50]=0;
dp[51]=3;
dp[52]=0;
dp[53]=0;
dp[54]=1;
dp[55]=6;
dp[56]=0;
dp[57]=6;
dp[58]=6;
dp[59]=0;
dp[60]=0;
dp[61]=6;
dp[62]=0;
dp[63]=0;
dp[64]=0;
dp[65]=0;
dp[66]=3;
dp[67]=3;
dp[68]=3;
dp[69]=6;
dp[70]=0;
dp[71]=6;
dp[72]=3;
dp[73]=6;
dp[74]=0;
dp[75]=0;
dp[76]=0;
dp[77]=6;
dp[78]=0;
dp[79]=0;
dp[80]=0;
dp[81]=3;
dp[82]=3;
dp[83]=9;
dp[84]=0;
dp[85]=6;
dp[86]=3;
dp[87]=6;
dp[88]=0;
dp[89]=3;
dp[90]=6;
dp[91]=0;
dp[92]=0;
dp[93]=0;
dp[94]=0;
dp[95]=6;
dp[96]=1;
dp[97]=6;
dp[98]=0;
dp[99]=6;
dp[100]=6;
dp[101]=0;
dp[102]=3;
dp[103]=12;
dp[104]=0;
dp[105]=6;
dp[106]=0;
dp[107]=0;
dp[108]=3;
dp[109]=6;
dp[110]=0;
dp[111]=0;
dp[112]=0;
dp[113]=3;
dp[114]=3;
dp[115]=12;
dp[116]=0;
dp[117]=6;
dp[118]=3;
dp[119]=6;
dp[120]=0;
dp[121]=3;
dp[122]=6;
dp[123]=9;
dp[124]=0;
dp[125]=6;
dp[126]=0;
dp[127]=0;
dp[128]=0;
dp[129]=3;
dp[130]=6;
dp[131]=3;
dp[132]=3;
dp[133]=6;
dp[134]=0;
dp[135]=6;
dp[136]=3;
dp[137]=12;
dp[138]=0;
dp[139]=3;
dp[140]=6;
dp[141]=6;
dp[142]=0;
dp[143]=6;
dp[144]=0;
dp[145]=6;
dp[146]=3;
dp[147]=6;
dp[148]=0;
dp[149]=0;
dp[150]=1;
dp[151]=6;
dp[152]=3;
dp[153]=12;
dp[154]=6;
dp[155]=0;
dp[156]=0;
dp[157]=12;
dp[158]=0;
dp[159]=6;
dp[160]=0;
dp[161]=6;
dp[162]=6;
dp[163]=12;
dp[164]=0;
dp[165]=0;
dp[166]=6;
dp[167]=0;
dp[168]=0;
dp[169]=6;
dp[170]=0;
dp[171]=12;
dp[172]=3;
dp[173]=6;
dp[174]=0;
dp[175]=6;
dp[176]=3;
dp[177]=9;
dp[178]=6;
dp[179]=3;
dp[180]=6;
dp[181]=6;
dp[182]=0;
dp[183]=6;
dp[184]=0;
dp[185]=6;
dp[186]=0;
dp[187]=15;
dp[188]=6;
dp[189]=0;
dp[190]=0;
dp[191]=6;
dp[192]=0;
dp[193]=3;
dp[194]=3;
dp[195]=12;
dp[196]=0;
dp[197]=12;
dp[198]=6;
dp[199]=6;
dp[200]=0;
dp[201]=3;
dp[202]=6;
dp[203]=6;
dp[204]=3;
dp[205]=12;
dp[206]=0;
dp[207]=6;
dp[208]=0;
dp[209]=9;
dp[210]=6;
dp[211]=0;
dp[212]=0;
dp[213]=6;
dp[214]=3;
dp[215]=12;
dp[216]=1;
dp[217]=6;
dp[218]=6;
dp[219]=6;
dp[220]=6;
dp[221]=0;
dp[222]=0;
dp[223]=18;
dp[224]=0;
dp[225]=12;
dp[226]=0;
dp[227]=3;
dp[228]=6;
dp[229]=12;
dp[230]=0;
dp[231]=0;
dp[232]=6;
dp[233]=3;
dp[234]=6;
dp[235]=12;
dp[236]=0;
dp[237]=12;
dp[238]=0;
dp[239]=0;
dp[240]=0;
dp[241]=9;
dp[242]=3;
dp[243]=9;
dp[244]=6;
dp[245]=12;
dp[246]=3;
dp[247]=12;
dp[248]=0;
dp[249]=3;
dp[250]=6;
dp[251]=6;
dp[252]=0;
dp[253]=12;
dp[254]=0;
dp[255]=12;
dp[256]=0;
dp[257]=9;
dp[258]=9;
dp[259]=0;
dp[260]=0;
dp[261]=6;
dp[262]=3;
dp[263]=6;
dp[264]=3;
dp[265]=12;
dp[266]=6;
dp[267]=9;
dp[268]=3;
dp[269]=6;
dp[270]=0;
dp[271]=12;
dp[272]=3;
dp[273]=6;
dp[274]=3;
dp[275]=9;
dp[276]=6;
dp[277]=12;
dp[278]=6;
dp[279]=6;
dp[280]=0;
dp[281]=6;
dp[282]=0;
dp[283]=9;
dp[284]=6;
dp[285]=6;
dp[286]=0;
dp[287]=12;
dp[288]=3;
dp[289]=6;
dp[290]=0;
dp[291]=9;
dp[292]=6;
dp[293]=6;
dp[294]=1;
dp[295]=6;
dp[296]=0;
dp[297]=21;
dp[298]=12;
dp[299]=6;
dp[300]=0;
dp[301]=12;
dp[302]=0;
dp[303]=12;
dp[304]=0;
dp[305]=0;
dp[306]=6;
dp[307]=15;
dp[308]=6;
dp[309]=0;
dp[310]=6;
dp[311]=12;
dp[312]=0;
dp[313]=12;
dp[314]=0;
dp[315]=12;
dp[316]=0;
dp[317]=0;
dp[318]=0;
dp[319]=12;
dp[320]=0;
dp[321]=12;
dp[322]=12;
dp[323]=3;
dp[324]=3;
dp[325]=18;
dp[326]=3;
dp[327]=6;
dp[328]=3;
dp[329]=6;
dp[330]=6;
dp[331]=9;
dp[332]=9;
dp[333]=18;
dp[334]=0;
dp[335]=6;
dp[336]=0;
dp[337]=12;
dp[338]=0;
dp[339]=9;
dp[340]=6;
dp[341]=0;
dp[342]=3;
dp[343]=12;
dp[344]=3;
dp[345]=6;
dp[346]=6;
dp[347]=12;
dp[348]=6;
dp[349]=6;
dp[350]=0;
dp[351]=0;
dp[352]=0;
dp[353]=15;
dp[354]=3;
dp[355]=18;
dp[356]=3;
dp[357]=18;
dp[358]=3;
dp[359]=12;
dp[360]=6;
dp[361]=3;
dp[362]=6;
dp[363]=9;
dp[364]=0;
dp[365]=12;
dp[366]=0;
dp[367]=12;
dp[368]=0;
dp[369]=18;
dp[370]=12;
dp[371]=0;
dp[372]=0;
dp[373]=12;
dp[374]=3;
dp[375]=6;
dp[376]=0;
dp[377]=6;
dp[378]=6;
dp[379]=9;
dp[380]=6;
dp[381]=0;
dp[382]=0;
dp[383]=18;
dp[384]=1;
dp[385]=18;
dp[386]=3;
dp[387]=12;
dp[388]=6;
dp[389]=6;
dp[390]=6;
dp[391]=12;
dp[392]=0;
dp[393]=15;
dp[394]=6;
dp[395]=12;
dp[396]=6;
dp[397]=18;
dp[398]=0;
dp[399]=0;
dp[400]=6;
dp[401]=0;
dp[402]=9;
dp[403]=12;
dp[404]=0;
dp[405]=18;
dp[406]=0;
dp[407]=6;
dp[408]=3;
dp[409]=12;
dp[410]=0;
dp[411]=12;
dp[412]=12;
dp[413]=0;
dp[414]=0;
dp[415]=12;
dp[416]=0;
dp[417]=3;
dp[418]=6;
dp[419]=12;
dp[420]=6;
dp[421]=18;
dp[422]=9;
dp[423]=18;
dp[424]=0;
dp[425]=9;
dp[426]=6;
dp[427]=18;
dp[428]=0;
dp[429]=6;
dp[430]=0;
dp[431]=6;
dp[432]=3;
dp[433]=27;
dp[434]=6;
dp[435]=6;
dp[436]=6;
dp[437]=6;
dp[438]=3;
dp[439]=6;
dp[440]=0;
dp[441]=12;
dp[442]=6;
dp[443]=9;
dp[444]=0;
dp[445]=6;
dp[446]=0;
dp[447]=18;
dp[448]=0;
dp[449]=9;
dp[450]=9;
dp[451]=15;
dp[452]=3;
dp[453]=12;
dp[454]=6;
dp[455]=6;
dp[456]=3;
dp[457]=9;
dp[458]=6;
dp[459]=12;
dp[460]=12;
dp[461]=18;
dp[462]=0;
dp[463]=18;
dp[464]=0;
dp[465]=6;
dp[466]=6;
dp[467]=21;
dp[468]=6;
dp[469]=0;
dp[470]=0;
dp[471]=6;
dp[472]=3;
dp[473]=15;
dp[474]=6;
dp[475]=12;
dp[476]=6;
dp[477]=18;
dp[478]=0;
dp[479]=0;
dp[480]=0;
dp[481]=12;
dp[482]=6;
dp[483]=6;
dp[484]=3;
dp[485]=6;
dp[486]=4;
dp[487]=18;
dp[488]=6;
dp[489]=12;
dp[490]=6;
dp[491]=3;
dp[492]=9;
dp[493]=30;
dp[494]=0;
dp[495]=18;
dp[496]=0;
dp[497]=6;
dp[498]=6;
dp[499]=12;
dp[500]=6;
dp[501]=6;
dp[502]=9;
dp[503]=12;
dp[504]=0;
dp[505]=18;
dp[506]=6;
dp[507]=18;
dp[508]=0;
dp[509]=6;
dp[510]=0;
dp[511]=12;
dp[512]=0;
dp[513]=6;
dp[514]=12;
dp[515]=6;
dp[516]=3;
dp[517]=18;
dp[518]=0;
dp[519]=6;
dp[520]=6;
dp[521]=6;
dp[522]=6;
dp[523]=15;
dp[524]=3;
dp[525]=24;
dp[526]=0;
dp[527]=6;
dp[528]=3;
dp[529]=18;
dp[530]=0;
dp[531]=12;
dp[532]=6;
dp[533]=12;
dp[534]=6;
dp[535]=24;
dp[536]=0;
dp[537]=15;
dp[538]=18;
dp[539]=9;
dp[540]=6;
dp[541]=0;
dp[542]=0;
dp[543]=18;
dp[544]=3;
dp[545]=6;
dp[546]=0;
dp[547]=15;
dp[548]=12;
dp[549]=12;
dp[550]=6;
dp[551]=6;
dp[552]=0;
dp[553]=18;
dp[554]=0;
dp[555]=6;
dp[556]=3;
dp[557]=12;
dp[558]=0;
dp[559]=12;
dp[560]=6;
dp[561]=6;
dp[562]=9;
dp[563]=9;
dp[564]=6;
dp[565]=24;
dp[566]=3;
dp[567]=24;
dp[568]=0;
dp[569]=9;
dp[570]=12;
dp[571]=6;
dp[572]=6;
dp[573]=12;
dp[574]=0;
dp[575]=12;
dp[576]=0;
dp[577]=21;
dp[578]=9;
dp[579]=15;
dp[580]=6;
dp[581]=12;
dp[582]=3;
dp[583]=18;
dp[584]=3;
dp[585]=12;
dp[586]=6;
dp[587]=12;
dp[588]=6;
dp[589]=0;
dp[590]=0;
dp[591]=12;
dp[592]=0;
dp[593]=12;
dp[594]=6;
dp[595]=24;
dp[596]=0;
dp[597]=6;
dp[598]=12;
dp[599]=6;
dp[600]=1;
dp[601]=9;
dp[602]=6;
dp[603]=12;
dp[604]=6;
dp[605]=24;
dp[606]=0;
dp[607]=18;
dp[608]=3;
dp[609]=12;
dp[610]=6;
dp[611]=6;
dp[612]=12;
dp[613]=24;
dp[614]=0;
dp[615]=12;
dp[616]=6;
dp[617]=15;
dp[618]=6;
dp[619]=18;
dp[620]=0;
dp[621]=18;
dp[622]=0;
dp[623]=0;
dp[624]=0;
dp[625]=18;
dp[626]=9;
dp[627]=21;
dp[628]=12;
dp[629]=0;
dp[630]=6;
dp[631]=18;
dp[632]=0;
dp[633]=9;
dp[634]=6;
dp[635]=6;
dp[636]=6;
dp[637]=12;
dp[638]=0;
dp[639]=12;
dp[640]=0;
dp[641]=9;
dp[642]=9;
dp[643]=27;
dp[644]=6;
dp[645]=6;
dp[646]=3;
dp[647]=18;
dp[648]=6;
dp[649]=21;
dp[650]=6;
dp[651]=6;
dp[652]=12;
dp[653]=12;
dp[654]=0;
dp[655]=12;
dp[656]=0;
dp[657]=24;
dp[658]=12;
dp[659]=0;
dp[660]=0;
dp[661]=24;
dp[662]=3;
dp[663]=24;
dp[664]=6;
dp[665]=12;
dp[666]=12;
dp[667]=18;
dp[668]=0;
dp[669]=0;
dp[670]=0;
dp[671]=12;
dp[672]=0;
dp[673]=18;
dp[674]=3;
dp[675]=15;
dp[676]=6;
dp[677]=12;
dp[678]=9;
dp[679]=6;
dp[680]=0;
dp[681]=15;
dp[682]=6;
dp[683]=9;
dp[684]=12;
dp[685]=24;
dp[686]=0;
dp[687]=12;
dp[688]=3;
dp[689]=6;
dp[690]=6;
dp[691]=21;
dp[692]=6;
dp[693]=18;
dp[694]=3;
dp[695]=18;
dp[696]=0;
dp[697]=21;
dp[698]=12;
dp[699]=15;
dp[700]=6;
dp[701]=6;
dp[702]=0;
dp[703]=12;
dp[704]=3;
dp[705]=12;
dp[706]=9;
dp[707]=18;
dp[708]=9;
dp[709]=12;
dp[710]=6;
dp[711]=6;
dp[712]=6;
dp[713]=24;
dp[714]=0;
dp[715]=18;
dp[716]=3;
dp[717]=24;
dp[718]=0;
dp[719]=6;
dp[720]=6;
dp[721]=0;
dp[722]=6;
dp[723]=9;
dp[724]=6;
dp[725]=6;
dp[726]=4;
dp[727]=30;
dp[728]=0;
dp[729]=18;
dp[730]=12;
dp[731]=9;
dp[732]=6;
dp[733]=24;
dp[734]=0;
dp[735]=18;
dp[736]=0;
dp[737]=9;
dp[738]=12;
dp[739]=21;
dp[740]=6;
dp[741]=6;
dp[742]=12;
dp[743]=12;
dp[744]=0;
dp[745]=18;
dp[746]=0;
dp[747]=21;
dp[748]=15;
dp[749]=12;
dp[750]=0;
dp[751]=12;
dp[752]=6;
dp[753]=12;
dp[754]=12;
dp[755]=18;
dp[756]=0;
dp[757]=18;
dp[758]=0;
dp[759]=6;
dp[760]=0;
dp[761]=9;
dp[762]=12;
dp[763]=18;
dp[764]=6;
dp[765]=30;
dp[766]=0;
dp[767]=0;
dp[768]=0;
dp[769]=24;
dp[770]=6;
dp[771]=9;
dp[772]=3;
dp[773]=12;
dp[774]=6;
dp[775]=30;
dp[776]=3;
dp[777]=6;
dp[778]=12;
dp[779]=6;
dp[780]=12;
dp[781]=12;
dp[782]=0;
dp[783]=36;
dp[784]=0;
dp[785]=6;
dp[786]=3;
dp[787]=27;
dp[788]=12;
dp[789]=12;
dp[790]=6;
dp[791]=6;
dp[792]=6;
dp[793]=24;
dp[794]=0;
dp[795]=12;
dp[796]=6;
dp[797]=12;
dp[798]=0;
dp[799]=18;
dp[800]=0;
dp[801]=18;
dp[802]=15;
dp[803]=18;
dp[804]=3;
dp[805]=18;
dp[806]=6;
dp[807]=12;
dp[808]=6;
dp[809]=6;
dp[810]=12;
dp[811]=3;
dp[812]=6;
dp[813]=6;
dp[814]=0;
dp[815]=12;
dp[816]=3;
dp[817]=39;
dp[818]=3;
dp[819]=12;
dp[820]=12;
dp[821]=12;
dp[822]=3;
dp[823]=18;
dp[824]=0;
dp[825]=21;
dp[826]=12;
dp[827]=21;
dp[828]=6;
dp[829]=18;
dp[830]=0;
dp[831]=12;
dp[832]=0;
dp[833]=9;
dp[834]=9;
dp[835]=12;
dp[836]=9;
dp[837]=24;
dp[838]=9;
dp[839]=12;
dp[840]=6;
dp[841]=12;
dp[842]=6;
dp[843]=33;
dp[844]=0;
dp[845]=6;
dp[846]=0;
dp[847]=18;
dp[848]=0;
dp[849]=9;
dp[850]=15;
dp[851]=12;
dp[852]=6;
dp[853]=24;
dp[854]=6;
dp[855]=6;
dp[856]=3;
dp[857]=15;
dp[858]=6;
dp[859]=15;
dp[860]=12;
dp[861]=18;
dp[862]=0;
dp[863]=18;
dp[864]=1;
dp[865]=18;
dp[866]=6;
dp[867]=12;
dp[868]=6;
dp[869]=6;
dp[870]=0;
dp[871]=24;
dp[872]=6;
dp[873]=24;
dp[874]=12;
dp[875]=18;
dp[876]=6;
dp[877]=24;
dp[878]=0;
dp[879]=6;
dp[880]=6;
dp[881]=12;
dp[882]=15;
dp[883]=24;
dp[884]=0;
dp[885]=24;
dp[886]=6;
dp[887]=6;
dp[888]=0;
dp[889]=18;
dp[890]=0;
dp[891]=15;
dp[892]=18;
dp[893]=12;
dp[894]=0;
dp[895]=24;
dp[896]=0;
dp[897]=12;
dp[898]=6;
dp[899]=12;
dp[900]=12;
dp[901]=18;
dp[902]=6;
dp[903]=24;
dp[904]=0;
dp[905]=0;
dp[906]=6;
dp[907]=24;
dp[908]=3;
dp[909]=12;
dp[910]=0;
dp[911]=12;
dp[912]=6;
dp[913]=30;
dp[914]=9;
dp[915]=6;
dp[916]=12;
dp[917]=24;
dp[918]=12;
dp[919]=12;
dp[920]=0;
dp[921]=15;
dp[922]=18;
dp[923]=12;
dp[924]=0;
dp[925]=18;
dp[926]=0;
dp[927]=24;
dp[928]=6;
dp[929]=15;
dp[930]=6;
dp[931]=18;
dp[932]=3;
dp[933]=18;
dp[934]=3;
dp[935]=12;
dp[936]=6;
dp[937]=24;
dp[938]=12;
dp[939]=12;
dp[940]=12;
dp[941]=6;
dp[942]=0;
dp[943]=36;
dp[944]=0;
dp[945]=18;
dp[946]=3;
dp[947]=6;
dp[948]=12;
dp[949]=6;
dp[950]=9;
dp[951]=12;
dp[952]=0;
dp[953]=3;
dp[954]=12;
dp[955]=36;
dp[956]=0;
dp[957]=30;
dp[958]=0;
dp[959]=12;
dp[960]=0;
dp[961]=18;
dp[962]=6;
dp[963]=12;
dp[964]=9;
dp[965]=12;
dp[966]=6;
dp[967]=24;
dp[968]=3;
dp[969]=18;
dp[970]=12;
dp[971]=15;
dp[972]=9;
dp[973]=24;
dp[974]=0;
dp[975]=18;
dp[976]=6;
dp[977]=18;
dp[978]=9;
dp[979]=18;
dp[980]=12;
dp[981]=6;
dp[982]=6;
dp[983]=24;
dp[984]=3;
dp[985]=24;
dp[986]=0;
dp[987]=12;
dp[988]=12;
dp[989]=12;
dp[990]=0;
dp[991]=6;
dp[992]=0;
dp[993]=27;
dp[994]=12;
dp[995]=18;
dp[996]=3;
dp[997]=30;
dp[998]=3;
dp[999]=18;
dp[1000]=6;
dp[1001]=0;
dp[1002]=12;
dp[1003]=15;
dp[1004]=6;
dp[1005]=18;
dp[1006]=0;
dp[1007]=24;
dp[1008]=0;
dp[1009]=9;
dp[1010]=6;
dp[1011]=9;
dp[1012]=12;
dp[1013]=18;
dp[1014]=7;
dp[1015]=24;
dp[1016]=0;
dp[1017]=24;
dp[1018]=12;
dp[1019]=15;
dp[1020]=12;
dp[1021]=24;
dp[1022]=0;
dp[1023]=24;
dp[1024]=0;
dp[1025]=6;
dp[1026]=9;
dp[1027]=30;
dp[1028]=9;
dp[1029]=6;
dp[1030]=6;
dp[1031]=0;
dp[1032]=9;
dp[1033]=33;
dp[1034]=12;
dp[1035]=36;
dp[1036]=0;
dp[1037]=12;
dp[1038]=0;
dp[1039]=18;
dp[1040]=0;
dp[1041]=6;
dp[1042]=21;
dp[1043]=12;
dp[1044]=6;
dp[1045]=36;
dp[1046]=6;
dp[1047]=0;
dp[1048]=3;
dp[1049]=18;
dp[1050]=6;
dp[1051]=12;
dp[1052]=6;
dp[1053]=24;
dp[1054]=0;
dp[1055]=12;
dp[1056]=3;
dp[1057]=24;
dp[1058]=6;
dp[1059]=9;
dp[1060]=12;
dp[1061]=6;
dp[1062]=6;
dp[1063]=30;
dp[1064]=6;
dp[1065]=18;
dp[1066]=12;
dp[1067]=9;
dp[1068]=9;
dp[1069]=12;
dp[1070]=0;
dp[1071]=30;
dp[1072]=3;
dp[1073]=18;
dp[1074]=3;
dp[1075]=27;
dp[1076]=6;
dp[1077]=30;
dp[1078]=12;
dp[1079]=12;
dp[1080]=0;
dp[1081]=24;
dp[1082]=0;
dp[1083]=27;
dp[1084]=12;
dp[1085]=6;
dp[1086]=0;
dp[1087]=24;
dp[1088]=3;
dp[1089]=18;
dp[1090]=18;
dp[1091]=9;
dp[1092]=6;
dp[1093]=18;
dp[1094]=0;
dp[1095]=12;
dp[1096]=3;
dp[1097]=33;
dp[1098]=18;
dp[1099]=12;
dp[1100]=9;
dp[1101]=6;
dp[1102]=0;
dp[1103]=12;
dp[1104]=6;
dp[1105]=30;
dp[1106]=0;
dp[1107]=24;
dp[1108]=12;
dp[1109]=12;
dp[1110]=0;
dp[1111]=30;
dp[1112]=6;
dp[1113]=6;
dp[1114]=6;
dp[1115]=0;
dp[1116]=6;
dp[1117]=24;
dp[1118]=0;
dp[1119]=12;
dp[1120]=0;
dp[1121]=18;
dp[1122]=15;
dp[1123]=33;
dp[1124]=6;
dp[1125]=30;
dp[1126]=15;
dp[1127]=18;
dp[1128]=0;
dp[1129]=9;
dp[1130]=12;
dp[1131]=24;
dp[1132]=9;
dp[1133]=12;
dp[1134]=0;
dp[1135]=18;
dp[1136]=6;
dp[1137]=27;
dp[1138]=18;
dp[1139]=15;
dp[1140]=6;
dp[1141]=18;
dp[1142]=3;
dp[1143]=24;
dp[1144]=0;
dp[1145]=6;
dp[1146]=6;
dp[1147]=36;
dp[1148]=12;
dp[1149]=18;
dp[1150]=0;
dp[1151]=12;
dp[1152]=3;
dp[1153]=30;
dp[1154]=3;
dp[1155]=12;
dp[1156]=6;
dp[1157]=12;
dp[1158]=15;
dp[1159]=6;
dp[1160]=0;
dp[1161]=18;
dp[1162]=12;
dp[1163]=15;
dp[1164]=9;
dp[1165]=30;
dp[1166]=0;
dp[1167]=18;
dp[1168]=6;
dp[1169]=12;
dp[1170]=12;
dp[1171]=18;
dp[1172]=6;
dp[1173]=6;
dp[1174]=3;
dp[1175]=24;
dp[1176]=1;
dp[1177]=27;
dp[1178]=12;
dp[1179]=18;
dp[1180]=6;
dp[1181]=18;
dp[1182]=0;
dp[1183]=24;
dp[1184]=0;
dp[1185]=18;
dp[1186]=15;
dp[1187]=15;
dp[1188]=21;
dp[1189]=30;
dp[1190]=6;
dp[1191]=12;
dp[1192]=12;
dp[1193]=18;
dp[1194]=0;
dp[1195]=30;
dp[1196]=6;
dp[1197]=24;
dp[1198]=0;
dp[1199]=6;
dp[1200]=0;
dp[1201]=18;
dp[1202]=6;
dp[1203]=36;
dp[1204]=12;
dp[1205]=6;
dp[1206]=6;
dp[1207]=36;
dp[1208]=0;
dp[1209]=6;
dp[1210]=12;
dp[1211]=12;
dp[1212]=12;
dp[1213]=24;
dp[1214]=0;
dp[1215]=30;
dp[1216]=0;
dp[1217]=9;
dp[1218]=6;
dp[1219]=18;
dp[1220]=0;
dp[1221]=18;
dp[1222]=12;
dp[1223]=12;
dp[1224]=6;
dp[1225]=24;
dp[1226]=6;
dp[1227]=9;
dp[1228]=15;
dp[1229]=12;
dp[1230]=0;
dp[1231]=12;
dp[1232]=6;
dp[1233]=30;
dp[1234]=9;
dp[1235]=18;
dp[1236]=0;
dp[1237]=42;
dp[1238]=3;
dp[1239]=18;
dp[1240]=6;
dp[1241]=12;
dp[1242]=18;
dp[1243]=33;
dp[1244]=12;
dp[1245]=12;
dp[1246]=0;
dp[1247]=18;
dp[1248]=0;
dp[1249]=21;
dp[1250]=12;
dp[1251]=12;
dp[1252]=12;
dp[1253]=24;
dp[1254]=6;
dp[1255]=30;
dp[1256]=0;
dp[1257]=27;
dp[1258]=18;
dp[1259]=6;
dp[1260]=12;
dp[1261]=6;
dp[1262]=0;
dp[1263]=24;
dp[1264]=0;
dp[1265]=18;
dp[1266]=15;
dp[1267]=30;
dp[1268]=0;
dp[1269]=18;
dp[1270]=12;
dp[1271]=6;
dp[1272]=0;
dp[1273]=21;
dp[1274]=6;
dp[1275]=21;
dp[1276]=12;
dp[1277]=24;
dp[1278]=0;
dp[1279]=30;
dp[1280]=0;
dp[1281]=6;
dp[1282]=6;
dp[1283]=6;
dp[1284]=12;
dp[1285]=24;
dp[1286]=0;
dp[1287]=30;
dp[1288]=12;
dp[1289]=9;
dp[1290]=12;
dp[1291]=21;
dp[1292]=3;
dp[1293]=24;
dp[1294]=0;
dp[1295]=12;
dp[1296]=3;
dp[1297]=21;
dp[1298]=18;
dp[1299]=9;
dp[1300]=18;
dp[1301]=18;
dp[1302]=6;
dp[1303]=30;
dp[1304]=3;
dp[1305]=42;
dp[1306]=6;
dp[1307]=21;
dp[1308]=6;
dp[1309]=30;
dp[1310]=0;
dp[1311]=6;
dp[1312]=3;
dp[1313]=24;
dp[1314]=9;
dp[1315]=36;
dp[1316]=6;
dp[1317]=6;
dp[1318]=9;
dp[1319]=12;
dp[1320]=6;
dp[1321]=18;
dp[1322]=12;
dp[1323]=33;
dp[1324]=9;
dp[1325]=12;
dp[1326]=0;
dp[1327]=24;
dp[1328]=9;
dp[1329]=9;
dp[1330]=6;
dp[1331]=3;
dp[1332]=18;
dp[1333]=36;
dp[1334]=6;
dp[1335]=18;
dp[1336]=0;
dp[1337]=24;
dp[1338]=6;
dp[1339]=6;
dp[1340]=6;
dp[1341]=18;
dp[1342]=0;
dp[1343]=12;
dp[1344]=0;
dp[1345]=30;
dp[1346]=3;
dp[1347]=39;
dp[1348]=12;
dp[1349]=12;
dp[1350]=7;
dp[1351]=18;
dp[1352]=0;
dp[1353]=15;
dp[1354]=18;
dp[1355]=18;
dp[1356]=9;
dp[1357]=36;
dp[1358]=0;
dp[1359]=24;
dp[1360]=6;
dp[1361]=6;
dp[1362]=18;
dp[1363]=30;
dp[1364]=0;
dp[1365]=18;
dp[1366]=9;
dp[1367]=18;
dp[1368]=3;
dp[1369]=24;
dp[1370]=6;
dp[1371]=21;
dp[1372]=12;
dp[1373]=24;
dp[1374]=0;
dp[1375]=30;
dp[1376]=3;
dp[1377]=33;
dp[1378]=24;
dp[1379]=12;
dp[1380]=6;
dp[1381]=18;
dp[1382]=6;
dp[1383]=6;
dp[1384]=6;
dp[1385]=18;
dp[1386]=6;
dp[1387]=18;
dp[1388]=12;
dp[1389]=18;
dp[1390]=0;
dp[1391]=24;
dp[1392]=6;
dp[1393]=36;
dp[1394]=3;
dp[1395]=18;
dp[1396]=6;
dp[1397]=0;
dp[1398]=12;
dp[1399]=30;
dp[1400]=0;
dp[1401]=9;
dp[1402]=24;
dp[1403]=18;
dp[1404]=0;
dp[1405]=24;
dp[1406]=0;
dp[1407]=18;
dp[1408]=0;
dp[1409]=0;
dp[1410]=12;
dp[1411]=30;
dp[1412]=15;
dp[1413]=30;
dp[1414]=6;
dp[1415]=18;
dp[1416]=3;
dp[1417]=30;
dp[1418]=0;
dp[1419]=24;
dp[1420]=18;
dp[1421]=12;
dp[1422]=0;
dp[1423]=36;
dp[1424]=3;
dp[1425]=24;
dp[1426]=12;
dp[1427]=15;
dp[1428]=18;
dp[1429]=18;
dp[1430]=6;
dp[1431]=24;
dp[1432]=3;
dp[1433]=24;
dp[1434]=12;
dp[1435]=18;
dp[1436]=12;
dp[1437]=24;
dp[1438]=0;
dp[1439]=0;
dp[1440]=6;
dp[1441]=39;
dp[1442]=6;
dp[1443]=24;
dp[1444]=3;
dp[1445]=18;
dp[1446]=3;
dp[1447]=42;
dp[1448]=6;
dp[1449]=12;
dp[1450]=12;
dp[1451]=15;
dp[1452]=9;
dp[1453]=30;
dp[1454]=0;
dp[1455]=12;
dp[1456]=0;
dp[1457]=18;
dp[1458]=6;
dp[1459]=18;
dp[1460]=12;
dp[1461]=24;
dp[1462]=15;
dp[1463]=12;
dp[1464]=0;
dp[1465]=12;
dp[1466]=12;
dp[1467]=30;
dp[1468]=12;
dp[1469]=12;
dp[1470]=0;
dp[1471]=18;
dp[1472]=0;
dp[1473]=15;
dp[1474]=15;
dp[1475]=18;
dp[1476]=18;
dp[1477]=30;
dp[1478]=3;
dp[1479]=24;
dp[1480]=12;
dp[1481]=9;
dp[1482]=6;
dp[1483]=48;
dp[1484]=0;
dp[1485]=18;
dp[1486]=0;
dp[1487]=30;
dp[1488]=0;
dp[1489]=21;
dp[1490]=6;
dp[1491]=12;
dp[1492]=12;
dp[1493]=24;
dp[1494]=12;
dp[1495]=18;
dp[1496]=3;
dp[1497]=48;
dp[1498]=24;
dp[1499]=6;
dp[1500]=6;
dp[1501]=18;
dp[1502]=0;
dp[1503]=36;
dp[1504]=0;
dp[1505]=12;
dp[1506]=15;
dp[1507]=27;
dp[1508]=6;
dp[1509]=12;
dp[1510]=12;
dp[1511]=18;
dp[1512]=6;
dp[1513]=27;
dp[1514]=6;
dp[1515]=12;
dp[1516]=9;
dp[1517]=18;
dp[1518]=0;
dp[1519]=24;
dp[1520]=6;
dp[1521]=18;
dp[1522]=18;
dp[1523]=21;
dp[1524]=0;
dp[1525]=36;
dp[1526]=0;
dp[1527]=12;
dp[1528]=0;
dp[1529]=18;
dp[1530]=12;
dp[1531]=21;
dp[1532]=18;
dp[1533]=24;
dp[1534]=0;
dp[1535]=12;
dp[1536]=1;
dp[1537]=18;
dp[1538]=9;
dp[1539]=21;
dp[1540]=18;
dp[1541]=6;
dp[1542]=9;
dp[1543]=42;
dp[1544]=3;
dp[1545]=36;
dp[1546]=12;
dp[1547]=12;
dp[1548]=12;
dp[1549]=30;
dp[1550]=0;
dp[1551]=12;
dp[1552]=6;
dp[1553]=21;
dp[1554]=12;
dp[1555]=36;
dp[1556]=6;
dp[1557]=24;
dp[1558]=9;
dp[1559]=12;
dp[1560]=6;
dp[1561]=12;
dp[1562]=12;
dp[1563]=24;
dp[1564]=12;
dp[1565]=18;
dp[1566]=0;
dp[1567]=42;
dp[1568]=0;
dp[1569]=15;
dp[1570]=6;
dp[1571]=15;
dp[1572]=15;
dp[1573]=42;
dp[1574]=6;
dp[1575]=30;
dp[1576]=6;
dp[1577]=12;
dp[1578]=12;
dp[1579]=18;
dp[1580]=12;
dp[1581]=18;
dp[1582]=0;
dp[1583]=6;
dp[1584]=6;
dp[1585]=36;
dp[1586]=0;
dp[1587]=30;
dp[1588]=18;
dp[1589]=6;
dp[1590]=0;
dp[1591]=6;
dp[1592]=0;
dp[1593]=30;
dp[1594]=18;
dp[1595]=18;
dp[1596]=0;
dp[1597]=42;
dp[1598]=0;
dp[1599]=18;
dp[1600]=6;
dp[1601]=15;
dp[1602]=18;
dp[1603]=24;
dp[1604]=0;
dp[1605]=12;
dp[1606]=6;
dp[1607]=36;
dp[1608]=9;
dp[1609]=33;
dp[1610]=12;
dp[1611]=12;
dp[1612]=12;
dp[1613]=18;
dp[1614]=0;
dp[1615]=36;
dp[1616]=0;
dp[1617]=21;
dp[1618]=21;
dp[1619]=15;
dp[1620]=18;
dp[1621]=18;
dp[1622]=15;
dp[1623]=18;
dp[1624]=0;
dp[1625]=18;
dp[1626]=6;
dp[1627]=42;
dp[1628]=6;
dp[1629]=24;
dp[1630]=0;
dp[1631]=18;
dp[1632]=3;
dp[1633]=42;
dp[1634]=6;
dp[1635]=18;
dp[1636]=12;
dp[1637]=12;
dp[1638]=12;
dp[1639]=18;
dp[1640]=0;
dp[1641]=15;
dp[1642]=12;
dp[1643]=18;
dp[1644]=12;
dp[1645]=36;
dp[1646]=0;
dp[1647]=30;
dp[1648]=12;
dp[1649]=3;
dp[1650]=21;
dp[1651]=18;
dp[1652]=0;
dp[1653]=30;
dp[1654]=6;
dp[1655]=24;
dp[1656]=0;
dp[1657]=27;
dp[1658]=12;
dp[1659]=18;
dp[1660]=12;
dp[1661]=6;
dp[1662]=0;
dp[1663]=12;
dp[1664]=0;
dp[1665]=36;
dp[1666]=15;
dp[1667]=15;
dp[1668]=3;
dp[1669]=36;
dp[1670]=12;
dp[1671]=18;
dp[1672]=6;
dp[1673]=30;
dp[1674]=6;
dp[1675]=33;
dp[1676]=12;
dp[1677]=12;
dp[1678]=0;
dp[1679]=12;
dp[1680]=6;
dp[1681]=24;
dp[1682]=6;
dp[1683]=54;
dp[1684]=18;
dp[1685]=12;
dp[1686]=3;
dp[1687]=36;
dp[1688]=9;
dp[1689]=9;
dp[1690]=12;
dp[1691]=12;
dp[1692]=18;
dp[1693]=36;
dp[1694]=0;
dp[1695]=6;
dp[1696]=0;
dp[1697]=21;
dp[1698]=15;
dp[1699]=27;
dp[1700]=9;
dp[1701]=24;
dp[1702]=12;
dp[1703]=30;
dp[1704]=6;
dp[1705]=24;
dp[1706]=6;
dp[1707]=27;
dp[1708]=18;
dp[1709]=12;
dp[1710]=0;
dp[1711]=30;
dp[1712]=0;
dp[1713]=21;
dp[1714]=12;
dp[1715]=18;
dp[1716]=6;
dp[1717]=30;
dp[1718]=0;
dp[1719]=18;
dp[1720]=0;
dp[1721]=21;
dp[1722]=18;
dp[1723]=21;
dp[1724]=6;
dp[1725]=30;
dp[1726]=0;
dp[1727]=24;
dp[1728]=3;
dp[1729]=6;
dp[1730]=6;
dp[1731]=15;
dp[1732]=27;
dp[1733]=12;
dp[1734]=10;
dp[1735]=42;
dp[1736]=6;
dp[1737]=36;
dp[1738]=12;
dp[1739]=12;
dp[1740]=6;
dp[1741]=24;
dp[1742]=0;
dp[1743]=24;
dp[1744]=6;
dp[1745]=12;
dp[1746]=12;
dp[1747]=48;
dp[1748]=6;
dp[1749]=18;
dp[1750]=12;
dp[1751]=0;
dp[1752]=3;
dp[1753]=51;
dp[1754]=6;
dp[1755]=30;
dp[1756]=6;
dp[1757]=24;
dp[1758]=0;
dp[1759]=24;
dp[1760]=0;
dp[1761]=30;
dp[1762]=21;
dp[1763]=15;
dp[1764]=12;
dp[1765]=24;
dp[1766]=9;
dp[1767]=18;
dp[1768]=6;
dp[1769]=18;
dp[1770]=12;
dp[1771]=30;
dp[1772]=9;
dp[1773]=24;
dp[1774]=0;
dp[1775]=18;
dp[1776]=0;
dp[1777]=27;
dp[1778]=18;
dp[1779]=9;
dp[1780]=6;
dp[1781]=18;
dp[1782]=9;
dp[1783]=54;
dp[1784]=0;
dp[1785]=18;
dp[1786]=24;
dp[1787]=21;
dp[1788]=18;
dp[1789]=12;
dp[1790]=0;
dp[1791]=24;
dp[1792]=0;
dp[1793]=12;
dp[1794]=0;
dp[1795]=30;
dp[1796]=9;
dp[1797]=30;
dp[1798]=12;
dp[1799]=6;
dp[1800]=9;
dp[1801]=24;
dp[1802]=6;
dp[1803]=15;
dp[1804]=15;
dp[1805]=18;
dp[1806]=0;
dp[1807]=30;
dp[1808]=3;
dp[1809]=33;
dp[1810]=18;
dp[1811]=21;
dp[1812]=12;
dp[1813]=42;
dp[1814]=3;
dp[1815]=30;
dp[1816]=6;
dp[1817]=6;
dp[1818]=24;
dp[1819]=27;
dp[1820]=6;
dp[1821]=12;
dp[1822]=0;
dp[1823]=24;
dp[1824]=3;
dp[1825]=42;
dp[1826]=6;
dp[1827]=42;
dp[1828]=9;
dp[1829]=12;
dp[1830]=6;
dp[1831]=18;
dp[1832]=6;
dp[1833]=24;
dp[1834]=12;
dp[1835]=12;
dp[1836]=12;
dp[1837]=54;
dp[1838]=0;
dp[1839]=6;
dp[1840]=12;
dp[1841]=18;
dp[1842]=6;
dp[1843]=18;
dp[1844]=18;
dp[1845]=30;
dp[1846]=12;
dp[1847]=30;
dp[1848]=0;
dp[1849]=18;
dp[1850]=0;
dp[1851]=27;
dp[1852]=18;
dp[1853]=24;
dp[1854]=0;
dp[1855]=18;
dp[1856]=0;
dp[1857]=15;
dp[1858]=24;
dp[1859]=21;
dp[1860]=6;
dp[1861]=24;
dp[1862]=3;
dp[1863]=36;
dp[1864]=6;
dp[1865]=6;
dp[1866]=6;
dp[1867]=45;
dp[1868]=21;
dp[1869]=18;
dp[1870]=0;
dp[1871]=18;
dp[1872]=6;
dp[1873]=33;
dp[1874]=3;
dp[1875]=18;
dp[1876]=0;
dp[1877]=24;
dp[1878]=15;
dp[1879]=30;
dp[1880]=0;
dp[1881]=30;
dp[1882]=24;
dp[1883]=12;
dp[1884]=6;
dp[1885]=36;
dp[1886]=0;
dp[1887]=24;
dp[1888]=3;
dp[1889]=21;
dp[1890]=24;
dp[1891]=18;
dp[1892]=15;
dp[1893]=30;
dp[1894]=3;
dp[1895]=12;
dp[1896]=6;
dp[1897]=42;
dp[1898]=12;
dp[1899]=12;
dp[1900]=12;
dp[1901]=6;
dp[1902]=0;
dp[1903]=54;
dp[1904]=6;
dp[1905]=30;
dp[1906]=15;
dp[1907]=24;
dp[1908]=18;
dp[1909]=24;
dp[1910]=6;
dp[1911]=12;
dp[1912]=0;
dp[1913]=9;
dp[1914]=6;
dp[1915]=30;
dp[1916]=0;
dp[1917]=48;
dp[1918]=0;
dp[1919]=24;
dp[1920]=0;
dp[1921]=15;
dp[1922]=12;
dp[1923]=39;
dp[1924]=12;
dp[1925]=24;
dp[1926]=6;
dp[1927]=24;
dp[1928]=6;
dp[1929]=15;
dp[1930]=30;
dp[1931]=12;
dp[1932]=6;
dp[1933]=24;
dp[1934]=0;
dp[1935]=24;
dp[1936]=3;
dp[1937]=24;
dp[1938]=12;
dp[1939]=24;
dp[1940]=6;
dp[1941]=6;
dp[1942]=18;
dp[1943]=12;
dp[1944]=4;
dp[1945]=54;
dp[1946]=6;
dp[1947]=21;
dp[1948]=18;
dp[1949]=18;
dp[1950]=0;
dp[1951]=36;
dp[1952]=6;
dp[1953]=24;
dp[1954]=9;
dp[1955]=30;
dp[1956]=12;
dp[1957]=24;
dp[1958]=9;
dp[1959]=36;
dp[1960]=6;
dp[1961]=12;
dp[1962]=18;
dp[1963]=42;
dp[1964]=3;
dp[1965]=30;
dp[1966]=0;
dp[1967]=6;
dp[1968]=9;
dp[1969]=21;
dp[1970]=6;
dp[1971]=12;
dp[1972]=30;
dp[1973]=30;
dp[1974]=6;
dp[1975]=30;
dp[1976]=0;
dp[1977]=27;
dp[1978]=12;
dp[1979]=9;
dp[1980]=18;
dp[1981]=30;
dp[1982]=0;
dp[1983]=36;
dp[1984]=0;
dp[1985]=18;
dp[1986]=9;
dp[1987]=42;
dp[1988]=6;
dp[1989]=24;
dp[1990]=12;
dp[1991]=0;
dp[1992]=6;
dp[1993]=51;
dp[1994]=12;
dp[1995]=24;
dp[1996]=12;
dp[1997]=12;
dp[1998]=0;
dp[1999]=18;
dp[2000]=6;
dp[2001]=12;
dp[2002]=18;
dp[2003]=6;
dp[2004]=6;
dp[2005]=36;
dp[2006]=3;
dp[2007]=54;
dp[2008]=9;
dp[2009]=18;
dp[2010]=6;
dp[2011]=27;
dp[2012]=12;
dp[2013]=18;
dp[2014]=0;
dp[2015]=30;
dp[2016]=0;
dp[2017]=39;
dp[2018]=9;
dp[2019]=18;
dp[2020]=18;
dp[2021]=12;
dp[2022]=9;
dp[2023]=30;
dp[2024]=6;
dp[2025]=21;
dp[2026]=12;
dp[2027]=27;
dp[2028]=18;
dp[2029]=24;
dp[2030]=0;
dp[2031]=12;
dp[2032]=0;
dp[2033]=42;
dp[2034]=18;
dp[2035]=42;
dp[2036]=6;
dp[2037]=24;
dp[2038]=15;
dp[2039]=18;
dp[2040]=0;
dp[2041]=24;
dp[2042]=12;
dp[2043]=45;
dp[2044]=12;
dp[2045]=6;
dp[2046]=0;
dp[2047]=54;
dp[2048]=0;
dp[2049]=15;
dp[2050]=21;
dp[2051]=6;
dp[2052]=6;
dp[2053]=30;
dp[2054]=6;
dp[2055]=18;
dp[2056]=12;
dp[2057]=24;
dp[2058]=18;
dp[2059]=30;
dp[2060]=6;
dp[2061]=36;
dp[2062]=0;
dp[2063]=12;
dp[2064]=3;
dp[2065]=24;
dp[2066]=12;
dp[2067]=18;
dp[2068]=18;
dp[2069]=18;
dp[2070]=12;
dp[2071]=24;
dp[2072]=0;
dp[2073]=33;
dp[2074]=12;
dp[2075]=27;
dp[2076]=6;
dp[2077]=42;
dp[2078]=0;
dp[2079]=18;
dp[2080]=6;
dp[2081]=9;
dp[2082]=15;
dp[2083]=30;
dp[2084]=6;
dp[2085]=30;
dp[2086]=6;
dp[2087]=12;
dp[2088]=6;
dp[2089]=18;
dp[2090]=6;
dp[2091]=33;
dp[2092]=15;
dp[2093]=30;
dp[2094]=0;
dp[2095]=36;
dp[2096]=3;
dp[2097]=27;
dp[2098]=21;
dp[2099]=33;
dp[2100]=24;
dp[2101]=30;
dp[2102]=9;
dp[2103]=24;
dp[2104]=0;
dp[2105]=12;
dp[2106]=18;
dp[2107]=33;
dp[2108]=6;
dp[2109]=6;
dp[2110]=0;
dp[2111]=18;
dp[2112]=3;
dp[2113]=57;
dp[2114]=12;
dp[2115]=24;
dp[2116]=18;
dp[2117]=30;
dp[2118]=9;
dp[2119]=18;
dp[2120]=0;
dp[2121]=18;
dp[2122]=12;
dp[2123]=27;
dp[2124]=12;
dp[2125]=36;
dp[2126]=0;
dp[2127]=36;
dp[2128]=6;
dp[2129]=12;
dp[2130]=6;
dp[2131]=27;
dp[2132]=12;
dp[2133]=30;
dp[2134]=9;
dp[2135]=24;
dp[2136]=6;
dp[2137]=39;
dp[2138]=18;
dp[2139]=12;
dp[2140]=24;
dp[2141]=12;
dp[2142]=0;
dp[2143]=30;
dp[2144]=0;
dp[2145]=30;
dp[2146]=6;
dp[2147]=15;
dp[2148]=15;
dp[2149]=18;
dp[2150]=3;
dp[2151]=24;
dp[2152]=18;
dp[2153]=9;
dp[2154]=12;
dp[2155]=30;
dp[2156]=9;
dp[2157]=30;
dp[2158]=0;
dp[2159]=18;
dp[2160]=6;
dp[2161]=42;
dp[2162]=18;
dp[2163]=30;
dp[2164]=0;
dp[2165]=6;
dp[2166]=10;
dp[2167]=48;
dp[2168]=0;
dp[2169]=24;
dp[2170]=12;
dp[2171]=12;
dp[2172]=18;
dp[2173]=48;
dp[2174]=0;
dp[2175]=30;
dp[2176]=3;
dp[2177]=30;
dp[2178]=15;
dp[2179]=18;
dp[2180]=6;
dp[2181]=24;
dp[2182]=18;
dp[2183]=18;
dp[2184]=0;
dp[2185]=42;
dp[2186]=6;
dp[2187]=36;
dp[2188]=15;
dp[2189]=24;
dp[2190]=0;
dp[2191]=42;
dp[2192]=12;
dp[2193]=21;
dp[2194]=24;
dp[2195]=12;
dp[2196]=12;
dp[2197]=24;
dp[2198]=0;
dp[2199]=12;
dp[2200]=6;
dp[2201]=18;
dp[2202]=18;
dp[2203]=60;
dp[2204]=6;
dp[2205]=30;
dp[2206]=0;
dp[2207]=12;
dp[2208]=0;
dp[2209]=24;
dp[2210]=0;
dp[2211]=12;
dp[2212]=18;
dp[2213]=30;
dp[2214]=15;
dp[2215]=42;
dp[2216]=0;
dp[2217]=33;
dp[2218]=30;
dp[2219]=6;
dp[2220]=6;
dp[2221]=12;
dp[2222]=0;
dp[2223]=42;
dp[2224]=3;
dp[2225]=27;
dp[2226]=6;
dp[2227]=33;
dp[2228]=12;
dp[2229]=36;
dp[2230]=12;
dp[2231]=18;
dp[2232]=0;
dp[2233]=30;
dp[2234]=6;
dp[2235]=18;
dp[2236]=12;
dp[2237]=12;
dp[2238]=0;
dp[2239]=18;
dp[2240]=6;
dp[2241]=15;
dp[2242]=27;
dp[2243]=27;
dp[2244]=6;
dp[2245]=42;
dp[2246]=6;
dp[2247]=36;
dp[2248]=9;
dp[2249]=18;
dp[2250]=30;
dp[2251]=33;
dp[2252]=9;
dp[2253]=30;
dp[2254]=0;
dp[2255]=6;
dp[2256]=6;
dp[2257]=54;
dp[2258]=6;
dp[2259]=36;
dp[2260]=24;
dp[2261]=24;
dp[2262]=0;
dp[2263]=30;
dp[2264]=3;
dp[2265]=12;
dp[2266]=6;
dp[2267]=21;
dp[2268]=24;
dp[2269]=30;
dp[2270]=0;
dp[2271]=24;
dp[2272]=0;
dp[2273]=24;
dp[2274]=12;
dp[2275]=42;
dp[2276]=9;
dp[2277]=42;
dp[2278]=21;
dp[2279]=12;
dp[2280]=12;
dp[2281]=27;
dp[2282]=12;
dp[2283]=27;
dp[2284]=6;
dp[2285]=12;
dp[2286]=0;
dp[2287]=48;
dp[2288]=6;
dp[2289]=12;
dp[2290]=18;
dp[2291]=12;
dp[2292]=12;
dp[2293]=36;
dp[2294]=6;
dp[2295]=30;
dp[2296]=0;
dp[2297]=24;
dp[2298]=0;
dp[2299]=42;
dp[2300]=12;
dp[2301]=12;
dp[2302]=0;
dp[2303]=36;
dp[2304]=0;
dp[2305]=24;
dp[2306]=15;
dp[2307]=21;
dp[2308]=21;
dp[2309]=18;
dp[2310]=6;
dp[2311]=12;
dp[2312]=9;
dp[2313]=36;
dp[2314]=18;
dp[2315]=18;
dp[2316]=15;
dp[2317]=42;
dp[2318]=0;
dp[2319]=18;
dp[2320]=6;
dp[2321]=9;
dp[2322]=18;
dp[2323]=48;
dp[2324]=12;
dp[2325]=30;
dp[2326]=9;
dp[2327]=24;
dp[2328]=3;
dp[2329]=33;
dp[2330]=6;
dp[2331]=18;
dp[2332]=18;
dp[2333]=18;
dp[2334]=0;
dp[2335]=36;
dp[2336]=3;
dp[2337]=54;
dp[2338]=24;
dp[2339]=3;
dp[2340]=12;
dp[2341]=36;
dp[2342]=9;
dp[2343]=36;
dp[2344]=6;
dp[2345]=30;
dp[2346]=12;
dp[2347]=36;
dp[2348]=12;
dp[2349]=24;
dp[2350]=0;
dp[2351]=18;
dp[2352]=6;
dp[2353]=24;
dp[2354]=6;
dp[2355]=42;
dp[2356]=0;
dp[2357]=24;
dp[2358]=18;
dp[2359]=18;
dp[2360]=0;
dp[2361]=9;
dp[2362]=30;
dp[2363]=39;
dp[2364]=12;
dp[2365]=42;
dp[2366]=0;
dp[2367]=36;
dp[2368]=0;
dp[2369]=12;
dp[2370]=12;
dp[2371]=21;
dp[2372]=12;
dp[2373]=18;
dp[2374]=12;
dp[2375]=24;
dp[2376]=6;
dp[2377]=45;
dp[2378]=6;
dp[2379]=18;
dp[2380]=24;
dp[2381]=18;
dp[2382]=0;
dp[2383]=36;
dp[2384]=0;
dp[2385]=42;
dp[2386]=15;
dp[2387]=18;
dp[2388]=6;
dp[2389]=24;
dp[2390]=6;
dp[2391]=12;
dp[2392]=12;
dp[2393]=18;
dp[2394]=12;
dp[2395]=30;
dp[2396]=6;
dp[2397]=18;
dp[2398]=0;
dp[2399]=30;
dp[2400]=1;
dp[2401]=30;
dp[2402]=9;
dp[2403]=57;
dp[2404]=9;
dp[2405]=12;
dp[2406]=9;
dp[2407]=48;
dp[2408]=6;
dp[2409]=21;
dp[2410]=24;
dp[2411]=18;
dp[2412]=12;
dp[2413]=66;
dp[2414]=0;
dp[2415]=18;
dp[2416]=6;
dp[2417]=9;
dp[2418]=24;
dp[2419]=24;
dp[2420]=24;
dp[2421]=30;
dp[2422]=12;
dp[2423]=18;
dp[2424]=0;
dp[2425]=48;
dp[2426]=6;
dp[2427]=24;
dp[2428]=18;
dp[2429]=18;
dp[2430]=0;
dp[2431]=24;
dp[2432]=3;
dp[2433]=27;
dp[2434]=18;
dp[2435]=24;
dp[2436]=12;
dp[2437]=36;
dp[2438]=6;
dp[2439]=48;
dp[2440]=6;
dp[2441]=15;
dp[2442]=18;
dp[2443]=42;
dp[2444]=6;
dp[2445]=24;
dp[2446]=0;
dp[2447]=12;
dp[2448]=12;
dp[2449]=36;
dp[2450]=6;
dp[2451]=6;
dp[2452]=24;
dp[2453]=12;
dp[2454]=3;
dp[2455]=48;
dp[2456]=0;
dp[2457]=48;
dp[2458]=18;
dp[2459]=0;
dp[2460]=12;
dp[2461]=18;
dp[2462]=0;
dp[2463]=36;
dp[2464]=6;
dp[2465]=18;
dp[2466]=9;
dp[2467]=54;
dp[2468]=15;
dp[2469]=12;
dp[2470]=12;
dp[2471]=6;
dp[2472]=6;
dp[2473]=39;
dp[2474]=6;
dp[2475]=24;
dp[2476]=18;
dp[2477]=42;
dp[2478]=0;
dp[2479]=30;
dp[2480]=0;
dp[2481]=33;
dp[2482]=18;
dp[2483]=24;
dp[2484]=18;
dp[2485]=18;
dp[2486]=9;
dp[2487]=18;
dp[2488]=0;
dp[2489]=15;
dp[2490]=18;
dp[2491]=54;
dp[2492]=0;
dp[2493]=36;
dp[2494]=0;
dp[2495]=24;
dp[2496]=0;
dp[2497]=48;
dp[2498]=24;
dp[2499]=15;
dp[2500]=18;
dp[2501]=18;
dp[2502]=12;
dp[2503]=42;
dp[2504]=9;
dp[2505]=24;
dp[2506]=12;
dp[2507]=36;
dp[2508]=21;
dp[2509]=30;
dp[2510]=0;
dp[2511]=36;
dp[2512]=12;
dp[2513]=24;
dp[2514]=3;
dp[2515]=30;
dp[2516]=0;
dp[2517]=48;
dp[2518]=15;
dp[2519]=12;
dp[2520]=6;
dp[2521]=15;
dp[2522]=18;
dp[2523]=18;
dp[2524]=18;
dp[2525]=24;
dp[2526]=0;
dp[2527]=30;
dp[2528]=0;
dp[2529]=24;
dp[2530]=24;
dp[2531]=18;
dp[2532]=9;
dp[2533]=72;
dp[2534]=0;
dp[2535]=30;
dp[2536]=6;
dp[2537]=21;
dp[2538]=18;
dp[2539]=30;
dp[2540]=6;
dp[2541]=24;
dp[2542]=0;
dp[2543]=0;
dp[2544]=6;
dp[2545]=24;
dp[2546]=18;
dp[2547]=42;
dp[2548]=12;
dp[2549]=6;
dp[2550]=15;
dp[2551]=36;
dp[2552]=0;
dp[2553]=30;
dp[2554]=18;
dp[2555]=30;
dp[2556]=12;
dp[2557]=24;
dp[2558]=0;
dp[2559]=6;
dp[2560]=0;
dp[2561]=18;
dp[2562]=12;
dp[2563]=54;
dp[2564]=9;
dp[2565]=36;
dp[2566]=9;
dp[2567]=36;
dp[2568]=9;
dp[2569]=30;
dp[2570]=6;
dp[2571]=27;
dp[2572]=27;
dp[2573]=24;
dp[2574]=0;
dp[2575]=54;
dp[2576]=6;
dp[2577]=21;
dp[2578]=18;
dp[2579]=21;
dp[2580]=6;
dp[2581]=36;
dp[2582]=15;
dp[2583]=36;
dp[2584]=3;
dp[2585]=30;
dp[2586]=12;
dp[2587]=6;
dp[2588]=18;
dp[2589]=30;
dp[2590]=0;
dp[2591]=18;
dp[2592]=6;
dp[2593]=54;
dp[2594]=0;
dp[2595]=30;
dp[2596]=21;
dp[2597]=36;
dp[2598]=9;
dp[2599]=30;
dp[2600]=6;
dp[2601]=30;
dp[2602]=24;
dp[2603]=24;
dp[2604]=6;
dp[2605]=30;
dp[2606]=0;
dp[2607]=36;
dp[2608]=12;
dp[2609]=9;
dp[2610]=24;
dp[2611]=24;
dp[2612]=12;
dp[2613]=18;
dp[2614]=9;
dp[2615]=30;
dp[2616]=0;
dp[2617]=48;
dp[2618]=12;
dp[2619]=24;
dp[2620]=12;
dp[2621]=12;
dp[2622]=0;
dp[2623]=48;
dp[2624]=0;
dp[2625]=18;
dp[2626]=12;
dp[2627]=24;
dp[2628]=24;
dp[2629]=30;
dp[2630]=6;
dp[2631]=18;
dp[2632]=12;
dp[2633]=21;
dp[2634]=12;
dp[2635]=24;
dp[2636]=0;
dp[2637]=66;
dp[2638]=0;
dp[2639]=12;
dp[2640]=0;
dp[2641]=30;
dp[2642]=9;
dp[2643]=24;
dp[2644]=24;
dp[2645]=18;
dp[2646]=13;
dp[2647]=42;
dp[2648]=3;
dp[2649]=18;
dp[2650]=18;
dp[2651]=27;
dp[2652]=24;
dp[2653]=24;
dp[2654]=0;
dp[2655]=30;
dp[2656]=6;
dp[2657]=15;
dp[2658]=18;
dp[2659]=39;
dp[2660]=12;
dp[2661]=12;
dp[2662]=9;
dp[2663]=36;
dp[2664]=12;
dp[2665]=54;
dp[2666]=12;
dp[2667]=42;
dp[2668]=18;
dp[2669]=6;
dp[2670]=0;
dp[2671]=36;
dp[2672]=0;
dp[2673]=51;
dp[2674]=18;
dp[2675]=12;
dp[2676]=0;
dp[2677]=66;
dp[2678]=12;
dp[2679]=24;
dp[2680]=0;
dp[2681]=6;
dp[2682]=24;
dp[2683]=51;
dp[2684]=12;
dp[2685]=24;
dp[2686]=0;
dp[2687]=24;
dp[2688]=0;
dp[2689]=33;
dp[2690]=6;
dp[2691]=18;
dp[2692]=18;
dp[2693]=30;
dp[2694]=6;
dp[2695]=42;
dp[2696]=3;
dp[2697]=18;
dp[2698]=30;
dp[2699]=15;
dp[2700]=15;
dp[2701]=30;
dp[2702]=0;
dp[2703]=30;
dp[2704]=6;
dp[2705]=30;
dp[2706]=12;
dp[2707]=48;
dp[2708]=12;
dp[2709]=24;
dp[2710]=12;
dp[2711]=12;
dp[2712]=9;
dp[2713]=36;
dp[2714]=6;
dp[2715]=36;
dp[2716]=6;
dp[2717]=12;
dp[2718]=0;
dp[2719]=30;
dp[2720]=0;
dp[2721]=24;
dp[2722]=21;
dp[2723]=24;
dp[2724]=15;
dp[2725]=42;
dp[2726]=12;
dp[2727]=24;
dp[2728]=6;
dp[2729]=9;
dp[2730]=18;
dp[2731]=15;
dp[2732]=9;
dp[2733]=42;
dp[2734]=0;
dp[2735]=24;
dp[2736]=12;
dp[2737]=66;
dp[2738]=12;
dp[2739]=30;
dp[2740]=24;
dp[2741]=6;
dp[2742]=9;
dp[2743]=54;
dp[2744]=0;
dp[2745]=36;
dp[2746]=12;
dp[2747]=21;
dp[2748]=12;
dp[2749]=36;
dp[2750]=0;
dp[2751]=24;
dp[2752]=3;
dp[2753]=24;
dp[2754]=15;
dp[2755]=36;
dp[2756]=6;
dp[2757]=30;
dp[2758]=24;
dp[2759]=12;
dp[2760]=6;
dp[2761]=33;
dp[2762]=6;
dp[2763]=39;
dp[2764]=21;
dp[2765]=30;
dp[2766]=0;
dp[2767]=42;
dp[2768]=6;
dp[2769]=12;
dp[2770]=30;
dp[2771]=30;
dp[2772]=18;
dp[2773]=36;
dp[2774]=0;
dp[2775]=48;
dp[2776]=3;
dp[2777]=36;
dp[2778]=12;
dp[2779]=30;
dp[2780]=18;
dp[2781]=18;
dp[2782]=0;
dp[2783]=24;
dp[2784]=0;
dp[2785]=30;
dp[2786]=6;
dp[2787]=33;
dp[2788]=21;
dp[2789]=24;
dp[2790]=6;
dp[2791]=18;
dp[2792]=12;
dp[2793]=24;
dp[2794]=12;
dp[2795]=12;
dp[2796]=15;
dp[2797]=48;
dp[2798]=0;
dp[2799]=24;
dp[2800]=6;
dp[2801]=21;
dp[2802]=21;
dp[2803]=60;
dp[2804]=6;
dp[2805]=24;
dp[2806]=12;
dp[2807]=18;
dp[2808]=0;
dp[2809]=30;
dp[2810]=12;
dp[2811]=15;
dp[2812]=12;
dp[2813]=24;
dp[2814]=0;
dp[2815]=24;
dp[2816]=3;
dp[2817]=60;
dp[2818]=27;
dp[2819]=18;
dp[2820]=12;
dp[2821]=30;
dp[2822]=3;
dp[2823]=24;
dp[2824]=9;
dp[2825]=21;
dp[2826]=12;
dp[2827]=60;
dp[2828]=18;
dp[2829]=24;
dp[2830]=0;
dp[2831]=24;
dp[2832]=9;
dp[2833]=33;
dp[2834]=6;
dp[2835]=36;
dp[2836]=12;
dp[2837]=24;
dp[2838]=15;
dp[2839]=42;
dp[2840]=6;
dp[2841]=27;
dp[2842]=36;
dp[2843]=27;
dp[2844]=6;
dp[2845]=42;
dp[2846]=0;
dp[2847]=42;
dp[2848]=6;
dp[2849]=12;
dp[2850]=15;
dp[2851]=15;
dp[2852]=24;
dp[2853]=42;
dp[2854]=18;
dp[2855]=12;
dp[2856]=0;
dp[2857]=33;
dp[2858]=6;
dp[2859]=21;
dp[2860]=18;
dp[2861]=24;
dp[2862]=0;
dp[2863]=48;
dp[2864]=3;
dp[2865]=36;
dp[2866]=9;
dp[2867]=24;
dp[2868]=24;
dp[2869]=30;
dp[2870]=6;
dp[2871]=36;
dp[2872]=0;
dp[2873]=39;
dp[2874]=18;
dp[2875]=60;
dp[2876]=6;
dp[2877]=18;
dp[2878]=0;
dp[2879]=12;
dp[2880]=6;
dp[2881]=21;
dp[2882]=27;
dp[2883]=30;
dp[2884]=0;
dp[2885]=18;
dp[2886]=6;
dp[2887]=42;
dp[2888]=6;
dp[2889]=42;
dp[2890]=18;
dp[2891]=24;
dp[2892]=9;
dp[2893]=48;
dp[2894]=0;
dp[2895]=6;
dp[2896]=6;
dp[2897]=18;
dp[2898]=18;
dp[2899]=18;
dp[2900]=6;
dp[2901]=18;
dp[2902]=15;
dp[2903]=30;
dp[2904]=4;
dp[2905]=60;
dp[2906]=12;
dp[2907]=30;
dp[2908]=30;
dp[2909]=18;
dp[2910]=0;
dp[2911]=36;
dp[2912]=0;
dp[2913]=27;
dp[2914]=18;
dp[2915]=30;
dp[2916]=18;
dp[2917]=48;
dp[2918]=9;
dp[2919]=30;
dp[2920]=12;
dp[2921]=18;
dp[2922]=6;
dp[2923]=42;
dp[2924]=9;
dp[2925]=48;
dp[2926]=0;
dp[2927]=18;
dp[2928]=6;
dp[2929]=42;
dp[2930]=6;
dp[2931]=30;
dp[2932]=24;
dp[2933]=12;
dp[2934]=3;
dp[2935]=36;
dp[2936]=0;
dp[2937]=36;
dp[2938]=36;
dp[2939]=15;
dp[2940]=18;
dp[2941]=30;
dp[2942]=0;
dp[2943]=66;
dp[2944]=0;
dp[2945]=12;
dp[2946]=18;
dp[2947]=42;
dp[2948]=9;
dp[2949]=24;
dp[2950]=15;
dp[2951]=18;
dp[2952]=12;
dp[2953]=54;
dp[2954]=6;
dp[2955]=18;
dp[2956]=21;
dp[2957]=36;
dp[2958]=0;
dp[2959]=30;
dp[2960]=6;
dp[2961]=24;
dp[2962]=24;
dp[2963]=12;
dp[2964]=6;
dp[2965]=24;
dp[2966]=9;
dp[2967]=36;
dp[2968]=12;
dp[2969]=6;
dp[2970]=12;
dp[2971]=45;
dp[2972]=12;
dp[2973]=36;
dp[2974]=0;
dp[2975]=36;
dp[2976]=0;
dp[2977]=48;
dp[2978]=3;
dp[2979]=24;
dp[2980]=18;
dp[2981]=12;
dp[2982]=24;
dp[2983]=36;
dp[2984]=0;
dp[2985]=30;
dp[2986]=12;
dp[2987]=30;
dp[2988]=21;
dp[2989]=30;
dp[2990]=0;
dp[2991]=6;
dp[2992]=15;
dp[2993]=18;
dp[2994]=15;
dp[2995]=66;
dp[2996]=12;
dp[2997]=42;
dp[2998]=3;
dp[2999]=12;
dp[3000]=0;
dp[3001]=39;
dp[3002]=12;
dp[3003]=30;
dp[3004]=12;
dp[3005]=18;
dp[3006]=0;
dp[3007]=54;
dp[3008]=6;
dp[3009]=30;
dp[3010]=24;
dp[3011]=9;
dp[3012]=12;
dp[3013]=60;
dp[3014]=12;
dp[3015]=30;
dp[3016]=12;
dp[3017]=30;
dp[3018]=24;
dp[3019]=24;
dp[3020]=18;
dp[3021]=30;
dp[3022]=0;
dp[3023]=36;
dp[3024]=0;
dp[3025]=27;
dp[3026]=9;
dp[3027]=45;
dp[3028]=18;
dp[3029]=24;
dp[3030]=12;
dp[3031]=24;
dp[3032]=0;
dp[3033]=36;
dp[3034]=24;
dp[3035]=12;
dp[3036]=6;
dp[3037]=60;
dp[3038]=0;
dp[3039]=18;
dp[3040]=0;
dp[3041]=24;
dp[3042]=15;
dp[3043]=51;
dp[3044]=9;
dp[3045]=24;
dp[3046]=12;
dp[3047]=30;
dp[3048]=12;
dp[3049]=27;
dp[3050]=18;
dp[3051]=51;
dp[3052]=18;
dp[3053]=24;
dp[3054]=0;
dp[3055]=36;
dp[3056]=6;
dp[3057]=27;
dp[3058]=27;
dp[3059]=12;
dp[3060]=30;
dp[3061]=36;
dp[3062]=6;
dp[3063]=30;
dp[3064]=0;
dp[3065]=12;
dp[3066]=6;
dp[3067]=42;
dp[3068]=0;
dp[3069]=18;
dp[3070]=0;
dp[3071]=18;
dp[3072]=0;
dp[3073]=48;
dp[3074]=12;
dp[3075]=45;
dp[3076]=24;
dp[3077]=6;
dp[3078]=15;
dp[3079]=42;
dp[3080]=6;
dp[3081]=12;
dp[3082]=18;
dp[3083]=27;
dp[3084]=9;
dp[3085]=54;
dp[3086]=0;
dp[3087]=42;
dp[3088]=3;
dp[3089]=33;
dp[3090]=12;
dp[3091]=15;
dp[3092]=12;
dp[3093]=54;
dp[3094]=18;
dp[3095]=30;
dp[3096]=6;
dp[3097]=36;
dp[3098]=18;
dp[3099]=21;
dp[3100]=30;
dp[3101]=18;
dp[3102]=0;
dp[3103]=48;
dp[3104]=3;
dp[3105]=30;
dp[3106]=18;
dp[3107]=36;
dp[3108]=6;
dp[3109]=18;
dp[3110]=0;
dp[3111]=18;
dp[3112]=12;
dp[3113]=57;
dp[3114]=24;
dp[3115]=42;
dp[3116]=6;
dp[3117]=24;
dp[3118]=0;
dp[3119]=18;
dp[3120]=12;
dp[3121]=36;
dp[3122]=18;
dp[3123]=30;
dp[3124]=12;
dp[3125]=36;
dp[3126]=3;
dp[3127]=78;
dp[3128]=0;
dp[3129]=24;
dp[3130]=6;
dp[3131]=6;
dp[3132]=36;
dp[3133]=42;
dp[3134]=0;
dp[3135]=24;
dp[3136]=0;
dp[3137]=21;
dp[3138]=15;
dp[3139]=33;
dp[3140]=6;
dp[3141]=42;
dp[3142]=18;
dp[3143]=12;
dp[3144]=3;
dp[3145]=30;
dp[3146]=12;
dp[3147]=30;
dp[3148]=27;
dp[3149]=24;
dp[3150]=0;
dp[3151]=42;
dp[3152]=12;
dp[3153]=39;
dp[3154]=12;
dp[3155]=30;
dp[3156]=12;
dp[3157]=30;
dp[3158]=15;
dp[3159]=30;
dp[3160]=6;
dp[3161]=12;
dp[3162]=24;
dp[3163]=54;
dp[3164]=6;
dp[3165]=24;
dp[3166]=0;
dp[3167]=18;
dp[3168]=6;
dp[3169]=33;
dp[3170]=12;
dp[3171]=18;
dp[3172]=24;
dp[3173]=24;
dp[3174]=7;
dp[3175]=30;
dp[3176]=0;
dp[3177]=60;
dp[3178]=24;
dp[3179]=21;
dp[3180]=12;
dp[3181]=30;
dp[3182]=0;
dp[3183]=48;
dp[3184]=6;
dp[3185]=18;
dp[3186]=15;
dp[3187]=39;
dp[3188]=12;
dp[3189]=18;
dp[3190]=18;
dp[3191]=18;
dp[3192]=0;
dp[3193]=48;
dp[3194]=12;
dp[3195]=54;
dp[3196]=18;
dp[3197]=42;
dp[3198]=0;
dp[3199]=30;
dp[3200]=0;
dp[3201]=15;
dp[3202]=30;
dp[3203]=27;
dp[3204]=18;
dp[3205]=72;
dp[3206]=0;
dp[3207]=30;
dp[3208]=15;
dp[3209]=12;
dp[3210]=12;
dp[3211]=30;
dp[3212]=18;
dp[3213]=36;
dp[3214]=0;
dp[3215]=6;
dp[3216]=3;
dp[3217]=60;
dp[3218]=15;
dp[3219]=24;
dp[3220]=18;
dp[3221]=6;
dp[3222]=18;
dp[3223]=54;
dp[3224]=6;
dp[3225]=21;
dp[3226]=24;
dp[3227]=24;
dp[3228]=12;
dp[3229]=30;
dp[3230]=0;
dp[3231]=30;
dp[3232]=6;
dp[3233]=30;
dp[3234]=15;
dp[3235]=54;
dp[3236]=6;
dp[3237]=48;
dp[3238]=12;
dp[3239]=30;
dp[3240]=12;
dp[3241]=36;
dp[3242]=0;
dp[3243]=24;
dp[3244]=3;
dp[3245]=24;
dp[3246]=0;
dp[3247]=54;
dp[3248]=6;
dp[3249]=18;
dp[3250]=30;
dp[3251]=15;
dp[3252]=6;
dp[3253]=42;
dp[3254]=9;
dp[3255]=36;
dp[3256]=0;
dp[3257]=21;
dp[3258]=30;
dp[3259]=15;
dp[3260]=12;
dp[3261]=12;
dp[3262]=0;
dp[3263]=24;
dp[3264]=3;
dp[3265]=72;
dp[3266]=0;
dp[3267]=51;
dp[3268]=39;
dp[3269]=24;
dp[3270]=12;
dp[3271]=30;
dp[3272]=3;
dp[3273]=33;
dp[3274]=18;
dp[3275]=15;
dp[3276]=12;
dp[3277]=42;
dp[3278]=0;
dp[3279]=30;
dp[3280]=12;
dp[3281]=27;
dp[3282]=24;
dp[3283]=51;
dp[3284]=12;
dp[3285]=42;
dp[3286]=12;
dp[3287]=18;
dp[3288]=3;
dp[3289]=42;
dp[3290]=12;
dp[3291]=39;
dp[3292]=18;
dp[3293]=12;
dp[3294]=0;
dp[3295]=30;
dp[3296]=0;
dp[3297]=24;
dp[3298]=21;
dp[3299]=21;
dp[3300]=21;
dp[3301]=30;
dp[3302]=6;
dp[3303]=66;
dp[3304]=12;
dp[3305]=12;
dp[3306]=6;
dp[3307]=69;
dp[3308]=21;
dp[3309]=30;
dp[3310]=0;
dp[3311]=24;
dp[3312]=6;
dp[3313]=45;
dp[3314]=12;
dp[3315]=12;
dp[3316]=18;
dp[3317]=42;
dp[3318]=12;
dp[3319]=18;
dp[3320]=0;
dp[3321]=39;
dp[3322]=30;
dp[3323]=33;
dp[3324]=12;
dp[3325]=54;
dp[3326]=0;
dp[3327]=12;
dp[3328]=0;
dp[3329]=12;
dp[3330]=18;
dp[3331]=36;
dp[3332]=9;
dp[3333]=30;
dp[3334]=9;
dp[3335]=24;
dp[3336]=9;
dp[3337]=60;
dp[3338]=12;
dp[3339]=30;
dp[3340]=12;
dp[3341]=12;
dp[3342]=0;
dp[3343]=42;
dp[3344]=9;
dp[3345]=42;
dp[3346]=18;
dp[3347]=45;
dp[3348]=24;
dp[3349]=42;
dp[3350]=6;
dp[3351]=12;
dp[3352]=9;
dp[3353]=24;
dp[3354]=6;
dp[3355]=30;
dp[3356]=12;
dp[3357]=42;
dp[3358]=0;
dp[3359]=30;
dp[3360]=6;
dp[3361]=15;
dp[3362]=15;
dp[3363]=30;
dp[3364]=12;
dp[3365]=18;
dp[3366]=12;
dp[3367]=54;
dp[3368]=6;
dp[3369]=21;
dp[3370]=30;
dp[3371]=12;
dp[3372]=33;
dp[3373]=60;
dp[3374]=0;
dp[3375]=48;
dp[3376]=0;
dp[3377]=30;
dp[3378]=15;
dp[3379]=42;
dp[3380]=6;
dp[3381]=24;
dp[3382]=24;
dp[3383]=30;
dp[3384]=0;
dp[3385]=36;
dp[3386]=18;
dp[3387]=33;
dp[3388]=18;
dp[3389]=12;
dp[3390]=0;
dp[3391]=60;
dp[3392]=0;
dp[3393]=72;
dp[3394]=15;
dp[3395]=12;
dp[3396]=9;
dp[3397]=30;
dp[3398]=12;
dp[3399]=24;
dp[3400]=15;
dp[3401]=21;
dp[3402]=24;
dp[3403]=51;
dp[3404]=12;
dp[3405]=24;
dp[3406]=0;
dp[3407]=24;
dp[3408]=6;
dp[3409]=12;
dp[3410]=6;
dp[3411]=33;
dp[3412]=24;
dp[3413]=36;
dp[3414]=9;
dp[3415]=54;
dp[3416]=6;
dp[3417]=27;
dp[3418]=24;
dp[3419]=30;
dp[3420]=6;
dp[3421]=48;
dp[3422]=0;
dp[3423]=24;
dp[3424]=3;
dp[3425]=36;
dp[3426]=27;
dp[3427]=42;
dp[3428]=15;
dp[3429]=18;
dp[3430]=18;
dp[3431]=12;
dp[3432]=6;
dp[3433]=54;
dp[3434]=6;
dp[3435]=30;
dp[3436]=15;
dp[3437]=36;
dp[3438]=0;
dp[3439]=12;
dp[3440]=12;
dp[3441]=18;
dp[3442]=24;
dp[3443]=21;
dp[3444]=18;
dp[3445]=30;
dp[3446]=3;
dp[3447]=60;
dp[3448]=0;
dp[3449]=33;
dp[3450]=12;
dp[3451]=36;
dp[3452]=18;
dp[3453]=48;
dp[3454]=0;
dp[3455]=24;
dp[3456]=1;
dp[3457]=39;
dp[3458]=12;
dp[3459]=24;
dp[3460]=18;
dp[3461]=24;
dp[3462]=9;
dp[3463]=66;
dp[3464]=6;
dp[3465]=48;
dp[3466]=24;
dp[3467]=12;
dp[3468]=12;
dp[3469]=42;
dp[3470]=0;
dp[3471]=24;
dp[3472]=6;
dp[3473]=18;
dp[3474]=12;
dp[3475]=63;
dp[3476]=6;
dp[3477]=36;
dp[3478]=24;
dp[3479]=18;
dp[3480]=0;
dp[3481]=39;
dp[3482]=12;
dp[3483]=39;
dp[3484]=24;
dp[3485]=24;
dp[3486]=0;
dp[3487]=54;
dp[3488]=6;
dp[3489]=15;
dp[3490]=24;
dp[3491]=15;
dp[3492]=24;
dp[3493]=48;
dp[3494]=3;
dp[3495]=36;
dp[3496]=12;
dp[3497]=12;
dp[3498]=24;
dp[3499]=39;
dp[3500]=18;
dp[3501]=36;
dp[3502]=0;
dp[3503]=42;
dp[3504]=6;
dp[3505]=42;
dp[3506]=6;
dp[3507]=60;
dp[3508]=24;
dp[3509]=12;
dp[3510]=18;
dp[3511]=18;
dp[3512]=0;
dp[3513]=45;
dp[3514]=6;
dp[3515]=6;
dp[3516]=6;
dp[3517]=72;
dp[3518]=0;
dp[3519]=30;
dp[3520]=6;
dp[3521]=24;
dp[3522]=9;
dp[3523]=36;
dp[3524]=12;
dp[3525]=24;
dp[3526]=9;
dp[3527]=30;
dp[3528]=15;
dp[3529]=36;
dp[3530]=18;
dp[3531]=33;
dp[3532]=24;
dp[3533]=6;
dp[3534]=0;
dp[3535]=54;
dp[3536]=0;
dp[3537]=33;
dp[3538]=36;
dp[3539]=18;
dp[3540]=24;
dp[3541]=36;
dp[3542]=6;
dp[3543]=18;
dp[3544]=6;
dp[3545]=24;
dp[3546]=18;
dp[3547]=75;
dp[3548]=6;
dp[3549]=18;
dp[3550]=0;
dp[3551]=18;
dp[3552]=0;
dp[3553]=48;
dp[3554]=9;
dp[3555]=36;
dp[3556]=18;
dp[3557]=42;
dp[3558]=9;
dp[3559]=30;
dp[3560]=0;
dp[3561]=27;
dp[3562]=36;
dp[3563]=24;
dp[3564]=15;
dp[3565]=42;
dp[3566]=0;
dp[3567]=42;
dp[3568]=18;
dp[3569]=36;
dp[3570]=12;
dp[3571]=18;
dp[3572]=12;
dp[3573]=72;
dp[3574]=9;
dp[3575]=24;
dp[3576]=0;
dp[3577]=54;
dp[3578]=18;
dp[3579]=21;
dp[3580]=24;
dp[3581]=12;
dp[3582]=0;
dp[3583]=60;
dp[3584]=0;
dp[3585]=24;
dp[3586]=24;
dp[3587]=39;
dp[3588]=12;
dp[3589]=42;
dp[3590]=18;
dp[3591]=30;
dp[3592]=6;
dp[3593]=9;
dp[3594]=12;
dp[3595]=48;
dp[3596]=12;
dp[3597]=30;
dp[3598]=0;
dp[3599]=18;
dp[3600]=12;
dp[3601]=36;
dp[3602]=15;
dp[3603]=48;
dp[3604]=18;
dp[3605]=18;
dp[3606]=3;
dp[3607]=42;
dp[3608]=6;
dp[3609]=42;
dp[3610]=18;
dp[3611]=18;
dp[3612]=24;
dp[3613]=54;
dp[3614]=0;
dp[3615]=36;
dp[3616]=0;
dp[3617]=24;
dp[3618]=36;
dp[3619]=42;
dp[3620]=0;
dp[3621]=12;
dp[3622]=27;
dp[3623]=30;
dp[3624]=6;
dp[3625]=60;
dp[3626]=6;
dp[3627]=30;
dp[3628]=24;
dp[3629]=12;
dp[3630]=0;
dp[3631]=36;
dp[3632]=3;
dp[3633]=42;
dp[3634]=12;
dp[3635]=18;
dp[3636]=12;
dp[3637]=36;
dp[3638]=9;
dp[3639]=30;
dp[3640]=0;
dp[3641]=15;
dp[3642]=18;
dp[3643]=33;
dp[3644]=12;
dp[3645]=54;
dp[3646]=0;
dp[3647]=30;
dp[3648]=6;
dp[3649]=33;
dp[3650]=21;
dp[3651]=27;
dp[3652]=30;
dp[3653]=42;
dp[3654]=12;
dp[3655]=54;
dp[3656]=9;
dp[3657]=42;
dp[3658]=24;
dp[3659]=27;
dp[3660]=6;
dp[3661]=36;
dp[3662]=0;
dp[3663]=24;
dp[3664]=12;
dp[3665]=24;
dp[3666]=12;
dp[3667]=45;
dp[3668]=24;
dp[3669]=12;
dp[3670]=6;
dp[3671]=30;
dp[3672]=12;
dp[3673]=69;
dp[3674]=12;
dp[3675]=42;
dp[3676]=12;
dp[3677]=30;
dp[3678]=0;
dp[3679]=24;
dp[3680]=0;
dp[3681]=42;
dp[3682]=18;
dp[3683]=24;
dp[3684]=15;
dp[3685]=60;
dp[3686]=9;
dp[3687]=48;
dp[3688]=18;
dp[3689]=18;
dp[3690]=24;
dp[3691]=27;
dp[3692]=12;
dp[3693]=36;
dp[3694]=0;
dp[3695]=30;
dp[3696]=0;
dp[3697]=54;
dp[3698]=9;
dp[3699]=30;
dp[3700]=18;
dp[3701]=24;
dp[3702]=15;
dp[3703]=48;
dp[3704]=0;
dp[3705]=24;
dp[3706]=24;
dp[3707]=45;
dp[3708]=24;
dp[3709]=24;
dp[3710]=0;
dp[3711]=18;
dp[3712]=6;
dp[3713]=36;
dp[3714]=9;
dp[3715]=54;
dp[3716]=15;
dp[3717]=24;
dp[3718]=12;
dp[3719]=12;
dp[3720]=6;
dp[3721]=18;
dp[3722]=12;
dp[3723]=54;
dp[3724]=18;
dp[3725]=12;
dp[3726]=0;
dp[3727]=60;
dp[3728]=3;
dp[3729]=48;
dp[3730]=30;
dp[3731]=12;
dp[3732]=18;
dp[3733]=60;
dp[3734]=6;
dp[3735]=24;
dp[3736]=3;
dp[3737]=36;
dp[3738]=12;
dp[3739]=33;
dp[3740]=12;
dp[3741]=36;
dp[3742]=0;
dp[3743]=36;
dp[3744]=6;
dp[3745]=36;
dp[3746]=3;
dp[3747]=33;
dp[3748]=24;
dp[3749]=12;
dp[3750]=13;
dp[3751]=42;
dp[3752]=12;
dp[3753]=27;
dp[3754]=18;
dp[3755]=30;
dp[3756]=12;
dp[3757]=54;
dp[3758]=0;
dp[3759]=30;
dp[3760]=12;
dp[3761]=21;
dp[3762]=39;
dp[3763]=54;
dp[3764]=6;
dp[3765]=54;
dp[3766]=18;
dp[3767]=18;
dp[3768]=0;
dp[3769]=33;
dp[3770]=12;
dp[3771]=36;
dp[3772]=36;
dp[3773]=36;
dp[3774]=0;
dp[3775]=30;
dp[3776]=0;
dp[3777]=42;
dp[3778]=33;
dp[3779]=18;
dp[3780]=18;
dp[3781]=36;
dp[3782]=12;
dp[3783]=30;
dp[3784]=3;
dp[3785]=30;
dp[3786]=12;
dp[3787]=66;
dp[3788]=6;
dp[3789]=30;
dp[3790]=0;
dp[3791]=18;
dp[3792]=12;
dp[3793]=63;
dp[3794]=18;
dp[3795]=24;
dp[3796]=6;
dp[3797]=30;
dp[3798]=12;
dp[3799]=48;
dp[3800]=9;
dp[3801]=6;
dp[3802]=24;
dp[3803]=30;
dp[3804]=12;
dp[3805]=42;
dp[3806]=0;
dp[3807]=72;
dp[3808]=0;
dp[3809]=30;
dp[3810]=12;
dp[3811]=48;
dp[3812]=3;
dp[3813]=24;
dp[3814]=15;
dp[3815]=12;
dp[3816]=12;
dp[3817]=66;
dp[3818]=18;
dp[3819]=9;
dp[3820]=36;
dp[3821]=12;
dp[3822]=0;
dp[3823]=54;
dp[3824]=0;
dp[3825]=54;
dp[3826]=18;
dp[3827]=15;
dp[3828]=30;
dp[3829]=36;
dp[3830]=6;
dp[3831]=12;
dp[3832]=0;
dp[3833]=21;
dp[3834]=18;
dp[3835]=54;
dp[3836]=12;
dp[3837]=30;
dp[3838]=0;
dp[3839]=6;
dp[3840]=0;
dp[3841]=36;
dp[3842]=15;
dp[3843]=60;
dp[3844]=18;
dp[3845]=18;
dp[3846]=15;
dp[3847]=48;
dp[3848]=6;
dp[3849]=27;
dp[3850]=24;
dp[3851]=21;
dp[3852]=12;
dp[3853]=54;
dp[3854]=0;
dp[3855]=54;
dp[3856]=9;
dp[3857]=12;
dp[3858]=24;
dp[3859]=48;
dp[3860]=12;
dp[3861]=48;
dp[3862]=15;
dp[3863]=54;
dp[3864]=6;
dp[3865]=36;
dp[3866]=6;
dp[3867]=39;
dp[3868]=24;
dp[3869]=24;
dp[3870]=0;
dp[3871]=24;
dp[3872]=3;
dp[3873]=33;
dp[3874]=24;
dp[3875]=18;
dp[3876]=18;
dp[3877]=66;
dp[3878]=12;
dp[3879]=18;
dp[3880]=12;
dp[3881]=30;
dp[3882]=12;
dp[3883]=75;
dp[3884]=15;
dp[3885]=36;
dp[3886]=0;
dp[3887]=30;
dp[3888]=9;
dp[3889]=24;
dp[3890]=6;
dp[3891]=21;
dp[3892]=24;
dp[3893]=24;
dp[3894]=12;
dp[3895]=60;
dp[3896]=0;
dp[3897]=66;
dp[3898]=36;
dp[3899]=12;
dp[3900]=18;
dp[3901]=36;
dp[3902]=0;
dp[3903]=24;
dp[3904]=6;
dp[3905]=30;
dp[3906]=18;
dp[3907]=39;
dp[3908]=18;
dp[3909]=30;
dp[3910]=12;
dp[3911]=24;
dp[3912]=9;
dp[3913]=30;
dp[3914]=6;
dp[3915]=36;
dp[3916]=18;
dp[3917]=18;
dp[3918]=0;
dp[3919]=54;
dp[3920]=12;
dp[3921]=33;
dp[3922]=24;
dp[3923]=36;
dp[3924]=6;
dp[3925]=66;
dp[3926]=0;
dp[3927]=30;
dp[3928]=6;
dp[3929]=12;
dp[3930]=12;
dp[3931]=33;
dp[3932]=24;
dp[3933]=54;
dp[3934]=0;
dp[3935]=18;
dp[3936]=3;
dp[3937]=60;
dp[3938]=3;
dp[3939]=30;
dp[3940]=24;
dp[3941]=24;
dp[3942]=21;
dp[3943]=48;
dp[3944]=0;
dp[3945]=18;
dp[3946]=30;
dp[3947]=51;
dp[3948]=12;
dp[3949]=18;
dp[3950]=0;
dp[3951]=30;
dp[3952]=12;
dp[3953]=33;
dp[3954]=15;
dp[3955]=18;
dp[3956]=12;
dp[3957]=30;
dp[3958]=27;
dp[3959]=24;
dp[3960]=0;
dp[3961]=48;
dp[3962]=12;
dp[3963]=45;
dp[3964]=6;
dp[3965]=30;
dp[3966]=0;
dp[3967]=72;
dp[3968]=0;
dp[3969]=51;
dp[3970]=18;
dp[3971]=27;
dp[3972]=27;
dp[3973]=54;
dp[3974]=9;
dp[3975]=48;
dp[3976]=12;
dp[3977]=27;
dp[3978]=30;
dp[3979]=36;
dp[3980]=18;
dp[3981]=18;
dp[3982]=0;
dp[3983]=42;
dp[3984]=3;
dp[3985]=36;
dp[3986]=9;
dp[3987]=45;
dp[3988]=30;
dp[3989]=6;
dp[3990]=6;
dp[3991]=36;
dp[3992]=3;
dp[3993]=51;
dp[3994]=24;
dp[3995]=24;
dp[3996]=18;
dp[3997]=72;
dp[3998]=0;
dp[3999]=18;
dp[4000]=6;
dp[4001]=9;
dp[4002]=36;
dp[4003]=42;
dp[4004]=0;
dp[4005]=36;
dp[4006]=9;
dp[4007]=30;
dp[4008]=12;
dp[4009]=60;
dp[4010]=30;
dp[4011]=24;
dp[4012]=15;
dp[4013]=24;
dp[4014]=0;
dp[4015]=36;
dp[4016]=6;
dp[4017]=30;
dp[4018]=27;
dp[4019]=27;
dp[4020]=18;
dp[4021]=42;
dp[4022]=12;
dp[4023]=48;
dp[4024]=0;
dp[4025]=42;
dp[4026]=0;
dp[4027]=33;
dp[4028]=24;
dp[4029]=24;
dp[4030]=0;
dp[4031]=30;
dp[4032]=0;
dp[4033]=42;
dp[4034]=12;
dp[4035]=48;
dp[4036]=9;
dp[4037]=36;
dp[4038]=9;
dp[4039]=24;
dp[4040]=6;
dp[4041]=27;
dp[4042]=36;
dp[4043]=12;
dp[4044]=9;
dp[4045]=60;
dp[4046]=0;
dp[4047]=30;
dp[4048]=12;
dp[4049]=15;
dp[4050]=18;
dp[4051]=42;
dp[4052]=18;
dp[4053]=36;
dp[4054]=18;
dp[4055]=24;
dp[4056]=7;
dp[4057]=48;
dp[4058]=12;
dp[4059]=54;
dp[4060]=24;
dp[4061]=30;
dp[4062]=0;
dp[4063]=78;
dp[4064]=0;
dp[4065]=18;
dp[4066]=18;
dp[4067]=27;
dp[4068]=24;
dp[4069]=24;
dp[4070]=6;
dp[4071]=30;
dp[4072]=12;
dp[4073]=33;
dp[4074]=18;
dp[4075]=60;
dp[4076]=15;
dp[4077]=54;
dp[4078]=0;
dp[4079]=12;
dp[4080]=12;
dp[4081]=36;
dp[4082]=12;
dp[4083]=36;
dp[4084]=24;
dp[4085]=30;
dp[4086]=18;
dp[4087]=54;
dp[4088]=0;
dp[4089]=18;
dp[4090]=18;
dp[4091]=18;
dp[4092]=24;
dp[4093]=84;
dp[4094]=0;
dp[4095]=54;
dp[4096]=0;
dp[4097]=27;
dp[4098]=15;
dp[4099]=42;
dp[4100]=6;
dp[4101]=36;
dp[4102]=12;
dp[4103]=18;
dp[4104]=9;
dp[4105]=54;
dp[4106]=6;
dp[4107]=30;
dp[4108]=30;
dp[4109]=24;
dp[4110]=0;
dp[4111]=30;
dp[4112]=9;
dp[4113]=60;
dp[4114]=30;
dp[4115]=36;
dp[4116]=6;
dp[4117]=42;
dp[4118]=12;
dp[4119]=30;
dp[4120]=6;
dp[4121]=6;
dp[4122]=30;
dp[4123]=60;
dp[4124]=0;
dp[4125]=18;
dp[4126]=0;
dp[4127]=24;
dp[4128]=9;
dp[4129]=51;
dp[4130]=18;
dp[4131]=24;
dp[4132]=33;
dp[4133]=30;
dp[4134]=0;
dp[4135]=42;
dp[4136]=12;
dp[4137]=60;
dp[4138]=18;
dp[4139]=18;
dp[4140]=36;
dp[4141]=18;
dp[4142]=0;
dp[4143]=24;
dp[4144]=0;
dp[4145]=18;
dp[4146]=9;
dp[4147]=78;
dp[4148]=12;
dp[4149]=48;
dp[4150]=24;
dp[4151]=12;
dp[4152]=0;
dp[4153]=48;
dp[4154]=6;
dp[4155]=12;
dp[4156]=18;
dp[4157]=42;
dp[4158]=0;
dp[4159]=48;
dp[4160]=0;
dp[4161]=30;
dp[4162]=27;
dp[4163]=18;
dp[4164]=6;
dp[4165]=48;
dp[4166]=3;
dp[4167]=66;
dp[4168]=21;
dp[4169]=18;
dp[4170]=18;
dp[4171]=33;
dp[4172]=12;
dp[4173]=48;
dp[4174]=0;
dp[4175]=30;
dp[4176]=6;
dp[4177]=63;
dp[4178]=21;
dp[4179]=18;
dp[4180]=36;
dp[4181]=24;
dp[4182]=15;
dp[4183]=60;
dp[4184]=6;
dp[4185]=36;
dp[4186]=30;
dp[4187]=36;
dp[4188]=0;
dp[4189]=48;
dp[4190]=0;
dp[4191]=48;
dp[4192]=3;
dp[4193]=36;
dp[4194]=30;
dp[4195]=42;
dp[4196]=18;
dp[4197]=24;
dp[4198]=24;
dp[4199]=12;
dp[4200]=6;
dp[4201]=21;
dp[4202]=6;
dp[4203]=72;
dp[4204]=12;
dp[4205]=36;
dp[4206]=0;
dp[4207]=60;
dp[4208]=6;
dp[4209]=12;
dp[4210]=18;
dp[4211]=15;
dp[4212]=24;
dp[4213]=60;
dp[4214]=9;
dp[4215]=30;
dp[4216]=0;
dp[4217]=39;
dp[4218]=30;
dp[4219]=54;
dp[4220]=12;
dp[4221]=18;
dp[4222]=0;
dp[4223]=18;
dp[4224]=3;
dp[4225]=60;
dp[4226]=9;
dp[4227]=57;
dp[4228]=24;
dp[4229]=6;
dp[4230]=18;
dp[4231]=48;
dp[4232]=6;
dp[4233]=60;
dp[4234]=18;
dp[4235]=18;
dp[4236]=9;
dp[4237]=48;
dp[4238]=0;
dp[4239]=24;
dp[4240]=12;
dp[4241]=18;
dp[4242]=18;
dp[4243]=39;
dp[4244]=6;
dp[4245]=42;
dp[4246]=15;
dp[4247]=36;
dp[4248]=6;
dp[4249]=36;
dp[4250]=18;
dp[4251]=18;
dp[4252]=30;
dp[4253]=18;
dp[4254]=0;
dp[4255]=42;
dp[4256]=6;
dp[4257]=39;
dp[4258]=27;
dp[4259]=27;
dp[4260]=18;
dp[4261]=48;
dp[4262]=12;
dp[4263]=42;
dp[4264]=12;
dp[4265]=24;
dp[4266]=18;
dp[4267]=27;
dp[4268]=9;
dp[4269]=30;
dp[4270]=0;
dp[4271]=24;
dp[4272]=9;
dp[4273]=81;
dp[4274]=12;
dp[4275]=72;
dp[4276]=12;
dp[4277]=30;
dp[4278]=6;
dp[4279]=36;
dp[4280]=0;
dp[4281]=33;
dp[4282]=42;
dp[4283]=39;
dp[4284]=30;
dp[4285]=42;
dp[4286]=0;
dp[4287]=12;
dp[4288]=3;
dp[4289]=12;
dp[4290]=6;
dp[4291]=24;
dp[4292]=18;
dp[4293]=48;
dp[4294]=12;
dp[4295]=48;
dp[4296]=3;
dp[4297]=63;
dp[4298]=24;
dp[4299]=24;
dp[4300]=27;
dp[4301]=30;
dp[4302]=0;
dp[4303]=78;
dp[4304]=6;
dp[4305]=36;
dp[4306]=18;
dp[4307]=36;
dp[4308]=30;
dp[4309]=30;
dp[4310]=12;
dp[4311]=36;
dp[4312]=12;
dp[4313]=30;
dp[4314]=6;
dp[4315]=60;
dp[4316]=12;
dp[4317]=48;
dp[4318]=0;
dp[4319]=24;
dp[4320]=0;
dp[4321]=36;
dp[4322]=21;
dp[4323]=30;
dp[4324]=24;
dp[4325]=30;
dp[4326]=12;
dp[4327]=48;
dp[4328]=0;
dp[4329]=36;
dp[4330]=12;
dp[4331]=24;
dp[4332]=27;
dp[4333]=36;
dp[4334]=0;
dp[4335]=42;
dp[4336]=12;
dp[4337]=27;
dp[4338]=24;
dp[4339]=54;
dp[4340]=6;
dp[4341]=18;
dp[4342]=12;
dp[4343]=48;
dp[4344]=0;
dp[4345]=30;
dp[4346]=6;
dp[4347]=72;
dp[4348]=24;
dp[4349]=12;
dp[4350]=0;
dp[4351]=30;
dp[4352]=3;
dp[4353]=45;
dp[4354]=24;
dp[4355]=0;
dp[4356]=18;
dp[4357]=78;
dp[4358]=15;
dp[4359]=18;
dp[4360]=18;
dp[4361]=39;
dp[4362]=18;
dp[4363]=39;
dp[4364]=9;
dp[4365]=36;
dp[4366]=0;
dp[4367]=24;
dp[4368]=6;
dp[4369]=39;
dp[4370]=12;
dp[4371]=30;
dp[4372]=18;
dp[4373]=30;
dp[4374]=16;
dp[4375]=48;
dp[4376]=0;
dp[4377]=36;
dp[4378]=30;
dp[4379]=12;
dp[4380]=12;
dp[4381]=60;
dp[4382]=0;
dp[4383]=42;
dp[4384]=3;
dp[4385]=24;
dp[4386]=21;
dp[4387]=84;
dp[4388]=33;
dp[4389]=30;
dp[4390]=12;
dp[4391]=18;
dp[4392]=18;
dp[4393]=48;
dp[4394]=12;
dp[4395]=36;
dp[4396]=12;
dp[4397]=30;
dp[4398]=0;
dp[4399]=48;
dp[4400]=9;
dp[4401]=42;
dp[4402]=36;
dp[4403]=42;
dp[4404]=6;
dp[4405]=48;
dp[4406]=3;
dp[4407]=42;
dp[4408]=0;
dp[4409]=33;
dp[4410]=24;
dp[4411]=30;
dp[4412]=12;
dp[4413]=36;
dp[4414]=0;
dp[4415]=36;
dp[4416]=6;
dp[4417]=54;
dp[4418]=12;
dp[4419]=30;
dp[4420]=30;
dp[4421]=6;
dp[4422]=21;
dp[4423]=66;
dp[4424]=0;
dp[4425]=39;
dp[4426]=24;
dp[4427]=36;
dp[4428]=24;
dp[4429]=36;
dp[4430]=0;
dp[4431]=24;
dp[4432]=12;
dp[4433]=30;
dp[4434]=15;
dp[4435]=54;
dp[4436]=12;
dp[4437]=78;
dp[4438]=30;
dp[4439]=6;
dp[4440]=0;
dp[4441]=33;
dp[4442]=12;
dp[4443]=27;
dp[4444]=30;
dp[4445]=30;
dp[4446]=0;
dp[4447]=36;
dp[4448]=6;
dp[4449]=18;
dp[4450]=36;
dp[4451]=36;
dp[4452]=6;
dp[4453]=66;
dp[4454]=3;
dp[4455]=60;
dp[4456]=6;
dp[4457]=18;
dp[4458]=30;
dp[4459]=42;
dp[4460]=0;
dp[4461]=12;
dp[4462]=0;
dp[4463]=36;
dp[4464]=6;
dp[4465]=54;
dp[4466]=6;
dp[4467]=33;
dp[4468]=24;
dp[4469]=24;
dp[4470]=12;
dp[4471]=54;
dp[4472]=0;
dp[4473]=42;
dp[4474]=12;
dp[4475]=15;
dp[4476]=12;
dp[4477]=60;
dp[4478]=0;
dp[4479]=30;
dp[4480]=0;
dp[4481]=21;
dp[4482]=18;
dp[4483]=75;
dp[4484]=18;
dp[4485]=48;
dp[4486]=18;
dp[4487]=18;
dp[4488]=15;
dp[4489]=30;
dp[4490]=24;
dp[4491]=42;
dp[4492]=33;
dp[4493]=36;
dp[4494]=0;
dp[4495]=30;
dp[4496]=6;
dp[4497]=45;
dp[4498]=24;
dp[4499]=9;
dp[4500]=30;
dp[4501]=36;
dp[4502]=3;
dp[4503]=54;
dp[4504]=15;
dp[4505]=24;
dp[4506]=18;
dp[4507]=63;
dp[4508]=18;
dp[4509]=42;
dp[4510]=0;
dp[4511]=24;
dp[4512]=0;
dp[4513]=75;
dp[4514]=6;
dp[4515]=30;
dp[4516]=9;
dp[4517]=30;
dp[4518]=15;
dp[4519]=42;
dp[4520]=12;
dp[4521]=33;
dp[4522]=36;
dp[4523]=21;
dp[4524]=24;
dp[4525]=60;
dp[4526]=0;
dp[4527]=54;
dp[4528]=9;
dp[4529]=30;
dp[4530]=30;
dp[4531]=48;
dp[4532]=12;
dp[4533]=18;
dp[4534]=12;
dp[4535]=24;
dp[4536]=0;
dp[4537]=66;
dp[4538]=12;
dp[4539]=24;
dp[4540]=18;
dp[4541]=36;
dp[4542]=0;
dp[4543]=72;
dp[4544]=6;
dp[4545]=36;
dp[4546]=15;
dp[4547]=27;
dp[4548]=27;
dp[4549]=30;
dp[4550]=6;
dp[4551]=12;
dp[4552]=18;
dp[4553]=24;
dp[4554]=6;
dp[4555]=78;
dp[4556]=15;
dp[4557]=42;
dp[4558]=0;
dp[4559]=12;
dp[4560]=6;
dp[4561]=27;
dp[4562]=24;
dp[4563]=51;
dp[4564]=18;
dp[4565]=36;
dp[4566]=12;
dp[4567]=60;
dp[4568]=3;
dp[4569]=51;
dp[4570]=30;
dp[4571]=12;
dp[4572]=24;
dp[4573]=36;
dp[4574]=0;
dp[4575]=30;
dp[4576]=0;
dp[4577]=48;
dp[4578]=12;
dp[4579]=21;
dp[4580]=6;
dp[4581]=36;
dp[4582]=24;
dp[4583]=54;
dp[4584]=6;
dp[4585]=42;
dp[4586]=6;
dp[4587]=36;
dp[4588]=36;
dp[4589]=6;
dp[4590]=0;
dp[4591]=54;
dp[4592]=12;
dp[4593]=27;
dp[4594]=15;
dp[4595]=18;
dp[4596]=18;
dp[4597]=66;
dp[4598]=6;
dp[4599]=42;
dp[4600]=0;
dp[4601]=15;
dp[4602]=30;
dp[4603]=63;
dp[4604]=12;
dp[4605]=48;
dp[4606]=0;
dp[4607]=36;
dp[4608]=3;
dp[4609]=63;
dp[4610]=12;
dp[4611]=36;
dp[4612]=30;
dp[4613]=18;
dp[4614]=9;
dp[4615]=48;
dp[4616]=3;
dp[4617]=48;
dp[4618]=36;
dp[4619]=30;
dp[4620]=12;
dp[4621]=42;
dp[4622]=0;
dp[4623]=72;
dp[4624]=6;
dp[4625]=36;
dp[4626]=30;
dp[4627]=30;
dp[4628]=12;
dp[4629]=24;
dp[4630]=12;
dp[4631]=6;
dp[4632]=15;
dp[4633]=75;
dp[4634]=18;
dp[4635]=30;
dp[4636]=6;
dp[4637]=36;
dp[4638]=0;
dp[4639]=24;
dp[4640]=0;
dp[4641]=18;
dp[4642]=36;
dp[4643]=48;
dp[4644]=18;
dp[4645]=60;
dp[4646]=18;
dp[4647]=60;
dp[4648]=12;
dp[4649]=33;
dp[4650]=12;
dp[4651]=33;
dp[4652]=15;
dp[4653]=72;
dp[4654]=0;
dp[4655]=18;
dp[4656]=9;
dp[4657]=54;
dp[4658]=15;
dp[4659]=21;
dp[4660]=30;
dp[4661]=36;
dp[4662]=12;
dp[4663]=30;
dp[4664]=0;
dp[4665]=42;
dp[4666]=24;
dp[4667]=48;
dp[4668]=18;
dp[4669]=36;
dp[4670]=0;
dp[4671]=24;
dp[4672]=6;
dp[4673]=18;
dp[4674]=15;
dp[4675]=81;
dp[4676]=12;
dp[4677]=12;
dp[4678]=27;
dp[4679]=36;
dp[4680]=12;
dp[4681]=30;
dp[4682]=6;
dp[4683]=36;
dp[4684]=18;
dp[4685]=24;
dp[4686]=0;
dp[4687]=48;
dp[4688]=6;
dp[4689]=36;
dp[4690]=36;
dp[4691]=27;
dp[4692]=6;
dp[4693]=48;
dp[4694]=9;
dp[4695]=36;
dp[4696]=3;
dp[4697]=36;
dp[4698]=36;
dp[4699]=36;
dp[4700]=24;
dp[4701]=30;
dp[4702]=0;
dp[4703]=24;
dp[4704]=1;
dp[4705]=42;
dp[4706]=6;
dp[4707]=66;
dp[4708]=27;
dp[4709]=24;
dp[4710]=18;
dp[4711]=48;
dp[4712]=12;
dp[4713]=51;
dp[4714]=18;
dp[4715]=24;
dp[4716]=18;
dp[4717]=84;
dp[4718]=0;
dp[4719]=24;
dp[4720]=6;
dp[4721]=12;
dp[4722]=9;
dp[4723]=63;
dp[4724]=18;
dp[4725]=48;
dp[4726]=9;
dp[4727]=30;
dp[4728]=0;
dp[4729]=36;
dp[4730]=12;
dp[4731]=33;
dp[4732]=24;
dp[4733]=30;
dp[4734]=0;
dp[4735]=72;
dp[4736]=0;
dp[4737]=42;
dp[4738]=48;
dp[4739]=36;
dp[4740]=18;
dp[4741]=42;
dp[4742]=12;
dp[4743]=42;
dp[4744]=15;
dp[4745]=24;
dp[4746]=12;
dp[4747]=60;
dp[4748]=15;
dp[4749]=24;
dp[4750]=0;
dp[4751]=12;
dp[4752]=21;
dp[4753]=72;
dp[4754]=3;
dp[4755]=42;
dp[4756]=30;
dp[4757]=24;
dp[4758]=18;
dp[4759]=36;
dp[4760]=6;
dp[4761]=42;
dp[4762]=18;
dp[4763]=30;
dp[4764]=12;
dp[4765]=42;
dp[4766]=0;
dp[4767]=48;
dp[4768]=12;
dp[4769]=12;
dp[4770]=24;
dp[4771]=24;
dp[4772]=18;
dp[4773]=66;
dp[4774]=6;
dp[4775]=24;
dp[4776]=0;
dp[4777]=93;
dp[4778]=12;
dp[4779]=51;
dp[4780]=30;
dp[4781]=12;
dp[4782]=0;
dp[4783]=54;
dp[4784]=6;
dp[4785]=18;
dp[4786]=27;
dp[4787]=24;
dp[4788]=24;
dp[4789]=36;
dp[4790]=12;
dp[4791]=30;
dp[4792]=0;
dp[4793]=45;
dp[4794]=18;
dp[4795]=60;
dp[4796]=6;
dp[4797]=54;
dp[4798]=0;
dp[4799]=24;
dp[4800]=0;
dp[4801]=51;
dp[4802]=24;
dp[4803]=21;
dp[4804]=18;
dp[4805]=30;
dp[4806]=6;
dp[4807]=72;
dp[4808]=6;
dp[4809]=6;
dp[4810]=18;
dp[4811]=21;
dp[4812]=36;
dp[4813]=42;
dp[4814]=0;
dp[4815]=48;
dp[4816]=12;
dp[4817]=27;
dp[4818]=24;
dp[4819]=36;
dp[4820]=6;
dp[4821]=30;
dp[4822]=27;
dp[4823]=30;
dp[4824]=6;
dp[4825]=39;
dp[4826]=18;
dp[4827]=51;
dp[4828]=36;
dp[4829]=30;
dp[4830]=0;
dp[4831]=42;
dp[4832]=0;
dp[4833]=66;
dp[4834]=18;
dp[4835]=36;
dp[4836]=6;
dp[4837]=66;
dp[4838]=9;
dp[4839]=24;
dp[4840]=12;
dp[4841]=24;
dp[4842]=24;
dp[4843]=78;
dp[4844]=12;
dp[4845]=36;
dp[4846]=0;
dp[4847]=36;
dp[4848]=12;
dp[4849]=60;
dp[4850]=15;
dp[4851]=42;
dp[4852]=24;
dp[4853]=6;
dp[4854]=15;
dp[4855]=54;
dp[4856]=0;
dp[4857]=33;
dp[4858]=30;
dp[4859]=21;
dp[4860]=30;
dp[4861]=42;
dp[4862]=0;
dp[4863]=54;
dp[4864]=0;
dp[4865]=24;
dp[4866]=9;
dp[4867]=60;
dp[4868]=9;
dp[4869]=36;
dp[4870]=24;
dp[4871]=24;
dp[4872]=6;
dp[4873]=66;
dp[4874]=12;
dp[4875]=48;
dp[4876]=18;
dp[4877]=54;
dp[4878]=0;
dp[4879]=30;
dp[4880]=0;
dp[4881]=30;
dp[4882]=39;
dp[4883]=30;
dp[4884]=18;
dp[4885]=48;
dp[4886]=6;
dp[4887]=42;
dp[4888]=12;
dp[4889]=33;
dp[4890]=24;
dp[4891]=33;
dp[4892]=12;
dp[4893]=60;
dp[4894]=0;
dp[4895]=18;
dp[4896]=6;
dp[4897]=42;
dp[4898]=24;
dp[4899]=42;
dp[4900]=24;
dp[4901]=6;
dp[4902]=12;
dp[4903]=72;
dp[4904]=6;
dp[4905]=42;
dp[4906]=30;
dp[4907]=18;
dp[4908]=9;
dp[4909]=30;
dp[4910]=0;
dp[4911]=24;
dp[4912]=15;
dp[4913]=30;
dp[4914]=18;
dp[4915]=60;
dp[4916]=12;
dp[4917]=54;
dp[4918]=15;
dp[4919]=24;
dp[4920]=0;
dp[4921]=48;
dp[4922]=24;
dp[4923]=33;
dp[4924]=12;
dp[4925]=36;
dp[4926]=0;
dp[4927]=66;
dp[4928]=6;
dp[4929]=36;
dp[4930]=18;
dp[4931]=21;
dp[4932]=30;
dp[4933]=72;
dp[4934]=3;
dp[4935]=24;
dp[4936]=9;
dp[4937]=27;
dp[4938]=30;
dp[4939]=30;
dp[4940]=18;
dp[4941]=42;
dp[4942]=0;
dp[4943]=42;
dp[4944]=0;
dp[4945]=72;
dp[4946]=6;
dp[4947]=39;
dp[4948]=42;
dp[4949]=24;
dp[4950]=18;
dp[4951]=60;
dp[4952]=3;
dp[4953]=24;
dp[4954]=18;
dp[4955]=36;
dp[4956]=18;
dp[4957]=30;
dp[4958]=0;
dp[4959]=54;
dp[4960]=6;
dp[4961]=27;
dp[4962]=33;
dp[4963]=60;
dp[4964]=12;
dp[4965]=24;
dp[4966]=24;
dp[4967]=18;
dp[4968]=18;
dp[4969]=30;
dp[4970]=12;
dp[4971]=21;
dp[4972]=33;
dp[4973]=48;
dp[4974]=0;
dp[4975]=78;
dp[4976]=12;
dp[4977]=78;
dp[4978]=12;
dp[4979]=30;
dp[4980]=12;
dp[4981]=42;
dp[4982]=12;
dp[4983]=48;
dp[4984]=0;
dp[4985]=24;
dp[4986]=12;
dp[4987]=75;
dp[4988]=18;
dp[4989]=24;
dp[4990]=0;
dp[4991]=18;
dp[4992]=0;
dp[4993]=33;
dp[4994]=24;
dp[4995]=30;
dp[4996]=21;
dp[4997]=42;
dp[4998]=15;
dp[4999]=30;
dp[5000]=12;
dp[5001]=39;
dp[5002]=30;
dp[5003]=51;
dp[5004]=12;
dp[5005]=54;
dp[5006]=0;
dp[5007]=36;
dp[5008]=12;
dp[5009]=18;
dp[5010]=12;
dp[5011]=48;
dp[5012]=24;
dp[5013]=78;
dp[5014]=18;
dp[5015]=18;
dp[5016]=6;
dp[5017]=78;
dp[5018]=6;
dp[5019]=24;
dp[5020]=30;
dp[5021]=12;
dp[5022]=0;
dp[5023]=42;
dp[5024]=0;
dp[5025]=45;
dp[5026]=18;
dp[5027]=15;
dp[5028]=27;
dp[5029]=42;
dp[5030]=0;
dp[5031]=54;
dp[5032]=18;
dp[5033]=36;
dp[5034]=18;
dp[5035]=36;
dp[5036]=6;
dp[5037]=48;
dp[5038]=0;
dp[5039]=30;
dp[5040]=12;
dp[5041]=36;
dp[5042]=21;
dp[5043]=45;
dp[5044]=6;
dp[5045]=24;
dp[5046]=7;
dp[5047]=54;
dp[5048]=0;
dp[5049]=27;
dp[5050]=42;
dp[5051]=33;
dp[5052]=24;
dp[5053]=72;
dp[5054]=0;
dp[5055]=42;
dp[5056]=0;
dp[5057]=48;
dp[5058]=24;
dp[5059]=45;
dp[5060]=18;
dp[5061]=18;
dp[5062]=15;
dp[5063]=36;
dp[5064]=15;
dp[5065]=66;
dp[5066]=6;
dp[5067]=66;
dp[5068]=30;
dp[5069]=18;
dp[5070]=0;
dp[5071]=48;
dp[5072]=0;
dp[5073]=27;
dp[5074]=39;
dp[5075]=30;
dp[5076]=18;
dp[5077]=66;
dp[5078]=27;
dp[5079]=12;
dp[5080]=12;
dp[5081]=18;
dp[5082]=24;
dp[5083]=60;
dp[5084]=6;
dp[5085]=66;
dp[5086]=0;
dp[5087]=42;
dp[5088]=0;
dp[5089]=42;
dp[5090]=6;
dp[5091]=33;
dp[5092]=21;
dp[5093]=36;
dp[5094]=12;
dp[5095]=42;
dp[5096]=6;
dp[5097]=21;
dp[5098]=36;
dp[5099]=33;
dp[5100]=21;
dp[5101]=48;
dp[5102]=0;
dp[5103]=66;
dp[5104]=12;
dp[5105]=6;
dp[5106]=18;
dp[5107]=75;
dp[5108]=24;
dp[5109]=36;
dp[5110]=12;
dp[5111]=18;
dp[5112]=0;
dp[5113]=81;
dp[5114]=12;
dp[5115]=42;
dp[5116]=30;
dp[5117]=36;
dp[5118]=0;
dp[5119]=24;
dp[5120]=0;
dp[5121]=30;
dp[5122]=30;
dp[5123]=30;
dp[5124]=6;
dp[5125]=60;
dp[5126]=9;
dp[5127]=60;
dp[5128]=6;
dp[5129]=24;
dp[5130]=30;
dp[5131]=30;
dp[5132]=6;
dp[5133]=30;
dp[5134]=0;
dp[5135]=30;
dp[5136]=12;
dp[5137]=75;
dp[5138]=18;
dp[5139]=30;
dp[5140]=24;
dp[5141]=24;
dp[5142]=15;
dp[5143]=78;
dp[5144]=0;
dp[5145]=42;
dp[5146]=24;
dp[5147]=18;
dp[5148]=30;
dp[5149]=42;
dp[5150]=0;
dp[5151]=30;
dp[5152]=12;
dp[5153]=21;
dp[5154]=12;
dp[5155]=48;
dp[5156]=9;
dp[5157]=60;
dp[5158]=21;
dp[5159]=30;
dp[5160]=12;
dp[5161]=24;
dp[5162]=24;
dp[5163]=39;
dp[5164]=21;
dp[5165]=24;
dp[5166]=0;
dp[5167]=54;
dp[5168]=3;
dp[5169]=39;
dp[5170]=30;
dp[5171]=33;
dp[5172]=24;
dp[5173]=72;
dp[5174]=12;
dp[5175]=60;
dp[5176]=0;
dp[5177]=18;
dp[5178]=24;
dp[5179]=57;
dp[5180]=12;
dp[5181]=24;
dp[5182]=0;
dp[5183]=24;
dp[5184]=3;
dp[5185]=90;
dp[5186]=9;
dp[5187]=12;
dp[5188]=21;
dp[5189]=36;
dp[5190]=12;
dp[5191]=30;
dp[5192]=18;
dp[5193]=84;
dp[5194]=24;
dp[5195]=30;
dp[5196]=9;
dp[5197]=60;
dp[5198]=0;
dp[5199]=36;
dp[5200]=18;
dp[5201]=18;
dp[5202]=24;
dp[5203]=78;
dp[5204]=18;
dp[5205]=24;
dp[5206]=18;
dp[5207]=48;
dp[5208]=6;
dp[5209]=24;
dp[5210]=0;
dp[5211]=45;
dp[5212]=30;
dp[5213]=24;
dp[5214]=0;
dp[5215]=66;
dp[5216]=3;
dp[5217]=60;
dp[5218]=36;
dp[5219]=21;
dp[5220]=42;
dp[5221]=42;
dp[5222]=6;
dp[5223]=30;
dp[5224]=6;
dp[5225]=33;
dp[5226]=12;
dp[5227]=60;
dp[5228]=21;
dp[5229]=36;
dp[5230]=0;
dp[5231]=6;
dp[5232]=6;
dp[5233]=36;
dp[5234]=15;
dp[5235]=36;
dp[5236]=30;
dp[5237]=48;
dp[5238]=21;
dp[5239]=48;
dp[5240]=0;
dp[5241]=39;
dp[5242]=36;
dp[5243]=36;
dp[5244]=6;
dp[5245]=54;
dp[5246]=0;
dp[5247]=66;
dp[5248]=3;
dp[5249]=18;
dp[5250]=18;
dp[5251]=33;
dp[5252]=24;
dp[5253]=36;
dp[5254]=18;
dp[5255]=30;
dp[5256]=9;
dp[5257]=66;
dp[5258]=6;
dp[5259]=15;
dp[5260]=36;
dp[5261]=24;
dp[5262]=0;
dp[5263]=96;
dp[5264]=6;
dp[5265]=30;
dp[5266]=12;
dp[5267]=42;
dp[5268]=6;
dp[5269]=36;
dp[5270]=6;
dp[5271]=36;
dp[5272]=9;
dp[5273]=27;
dp[5274]=36;
dp[5275]=42;
dp[5276]=12;
dp[5277]=42;
dp[5278]=0;
dp[5279]=18;
dp[5280]=6;
dp[5281]=51;
dp[5282]=12;
dp[5283]=78;
dp[5284]=18;
dp[5285]=30;
dp[5286]=9;
dp[5287]=54;
dp[5288]=12;
dp[5289]=39;
dp[5290]=24;
dp[5291]=24;
dp[5292]=33;
dp[5293]=66;
dp[5294]=0;
dp[5295]=36;
dp[5296]=9;
dp[5297]=45;
dp[5298]=33;
dp[5299]=36;
dp[5300]=12;
dp[5301]=18;
dp[5302]=27;
dp[5303]=36;
dp[5304]=0;
dp[5305]=78;
dp[5306]=12;
dp[5307]=48;
dp[5308]=24;
dp[5309]=30;
dp[5310]=0;
dp[5311]=42;
dp[5312]=9;
dp[5313]=48;
dp[5314]=21;
dp[5315]=18;
dp[5316]=9;
dp[5317]=60;
dp[5318]=12;
dp[5319]=54;
dp[5320]=6;
dp[5321]=21;
dp[5322]=24;
dp[5323]=72;
dp[5324]=3;
dp[5325]=66;
dp[5326]=0;
dp[5327]=18;
dp[5328]=18;
dp[5329]=33;
dp[5330]=12;
dp[5331]=21;
dp[5332]=36;
dp[5333]=36;
dp[5334]=6;
dp[5335]=36;
dp[5336]=6;
dp[5337]=60;
dp[5338]=36;
dp[5339]=36;
dp[5340]=18;
dp[5341]=48;
dp[5342]=0;
dp[5343]=24;
dp[5344]=0;
dp[5345]=30;
dp[5346]=24;
dp[5347]=87;
dp[5348]=24;
dp[5349]=24;
dp[5350]=27;
dp[5351]=42;
dp[5352]=6;
dp[5353]=60;
dp[5354]=18;
dp[5355]=66;
dp[5356]=6;
dp[5357]=18;
dp[5358]=0;
dp[5359]=36;
dp[5360]=6;
dp[5361]=39;
dp[5362]=36;
dp[5363]=30;
dp[5364]=18;
dp[5365]=36;
dp[5366]=9;
dp[5367]=30;
dp[5368]=0;
dp[5369]=18;
dp[5370]=18;
dp[5371]=51;
dp[5372]=12;
dp[5373]=48;
dp[5374]=0;
dp[5375]=54;
dp[5376]=0;
dp[5377]=48;
dp[5378]=18;
dp[5379]=36;
dp[5380]=30;
dp[5381]=36;
dp[5382]=30;
dp[5383]=66;
dp[5384]=3;
dp[5385]=12;
dp[5386]=18;
dp[5387]=15;
dp[5388]=39;
dp[5389]=60;
dp[5390]=0;
dp[5391]=24;
dp[5392]=12;
dp[5393]=66;
dp[5394]=6;
dp[5395]=54;
dp[5396]=12;
dp[5397]=48;
dp[5398]=6;
dp[5399]=18;
dp[5400]=7;
dp[5401]=30;
dp[5402]=24;
dp[5403]=48;
dp[5404]=18;
dp[5405]=30;
dp[5406]=0;
dp[5407]=84;
dp[5408]=0;
dp[5409]=30;
dp[5410]=48;
dp[5411]=12;
dp[5412]=15;
dp[5413]=60;
dp[5414]=9;
dp[5415]=42;
dp[5416]=18;
dp[5417]=42;
dp[5418]=18;
dp[5419]=42;
dp[5420]=18;
dp[5421]=48;
dp[5422]=0;
dp[5423]=30;
dp[5424]=9;
dp[5425]=48;
dp[5426]=21;
dp[5427]=69;
dp[5428]=36;
dp[5429]=12;
dp[5430]=12;
dp[5431]=48;
dp[5432]=0;
dp[5433]=57;
dp[5434]=18;
dp[5435]=24;
dp[5436]=24;
dp[5437]=66;
dp[5438]=0;
dp[5439]=36;
dp[5440]=6;
dp[5441]=24;
dp[5442]=21;
dp[5443]=69;
dp[5444]=6;
dp[5445]=54;
dp[5446]=12;
dp[5447]=30;
dp[5448]=18;
dp[5449]=72;
dp[5450]=18;
dp[5451]=30;
dp[5452]=30;
dp[5453]=18;
dp[5454]=0;
dp[5455]=42;
dp[5456]=0;
dp[5457]=42;
dp[5458]=42;
dp[5459]=12;
dp[5460]=18;
dp[5461]=42;
dp[5462]=6;
dp[5463]=54;
dp[5464]=9;
dp[5465]=42;
dp[5466]=12;
dp[5467]=72;
dp[5468]=18;
dp[5469]=24;
dp[5470]=0;
dp[5471]=24;
dp[5472]=3;
dp[5473]=78;
dp[5474]=0;
dp[5475]=24;
dp[5476]=24;
dp[5477]=30;
dp[5478]=15;
dp[5479]=60;
dp[5480]=6;
dp[5481]=42;
dp[5482]=30;
dp[5483]=39;
dp[5484]=21;
dp[5485]=36;
dp[5486]=0;
dp[5487]=54;
dp[5488]=12;
dp[5489]=27;
dp[5490]=24;
dp[5491]=42;
dp[5492]=24;
dp[5493]=72;
dp[5494]=21;
dp[5495]=30;
dp[5496]=0;
dp[5497]=48;
dp[5498]=18;
dp[5499]=24;
dp[5500]=30;
dp[5501]=12;
dp[5502]=0;
dp[5503]=30;
dp[5504]=3;
dp[5505]=24;
dp[5506]=15;
dp[5507]=72;
dp[5508]=33;
dp[5509]=42;
dp[5510]=6;
dp[5511]=24;
dp[5512]=24;
dp[5513]=12;
dp[5514]=24;
dp[5515]=66;
dp[5516]=12;
dp[5517]=60;
dp[5518]=0;
dp[5519]=24;
dp[5520]=6;
dp[5521]=63;
dp[5522]=12;
dp[5523]=42;
dp[5524]=18;
dp[5525]=24;
dp[5526]=18;
dp[5527]=84;
dp[5528]=6;
dp[5529]=30;
dp[5530]=24;
dp[5531]=24;
dp[5532]=6;
dp[5533]=90;
dp[5534]=0;
dp[5535]=72;
dp[5536]=6;
dp[5537]=21;
dp[5538]=24;
dp[5539]=30;
dp[5540]=18;
dp[5541]=18;
dp[5542]=30;
dp[5543]=24;
dp[5544]=6;
dp[5545]=66;
dp[5546]=18;
dp[5547]=54;
dp[5548]=18;
dp[5549]=36;
dp[5550]=0;
dp[5551]=36;
dp[5552]=12;
dp[5553]=60;
dp[5554]=27;
dp[5555]=30;
dp[5556]=18;
dp[5557]=90;
dp[5558]=18;
dp[5559]=18;
dp[5560]=0;
dp[5561]=18;
dp[5562]=24;
dp[5563]=48;
dp[5564]=24;
dp[5565]=30;
dp[5566]=0;
dp[5567]=36;
dp[5568]=6;
dp[5569]=36;
dp[5570]=18;
dp[5571]=66;
dp[5572]=36;
dp[5573]=30;
dp[5574]=3;
dp[5575]=66;
dp[5576]=3;
dp[5577]=57;
dp[5578]=48;
dp[5579]=12;
dp[5580]=18;
dp[5581]=36;
dp[5582]=0;
dp[5583]=48;
dp[5584]=6;
dp[5585]=36;
dp[5586]=21;
dp[5587]=48;
dp[5588]=0;
dp[5589]=60;
dp[5590]=12;
dp[5591]=36;
dp[5592]=12;
dp[5593]=72;
dp[5594]=0;
dp[5595]=36;
dp[5596]=30;
dp[5597]=30;
dp[5598]=0;
dp[5599]=48;
dp[5600]=0;
dp[5601]=33;
dp[5602]=30;
dp[5603]=48;
dp[5604]=9;
dp[5605]=54;
dp[5606]=9;
dp[5607]=36;
dp[5608]=24;
dp[5609]=18;
dp[5610]=30;
dp[5611]=42;
dp[5612]=18;
dp[5613]=54;
dp[5614]=0;
dp[5615]=12;
dp[5616]=0;
dp[5617]=54;
dp[5618]=12;
dp[5619]=21;
dp[5620]=24;
dp[5621]=30;
dp[5622]=21;
dp[5623]=72;
dp[5624]=0;
dp[5625]=66;
dp[5626]=24;
dp[5627]=27;
dp[5628]=18;
dp[5629]=36;
dp[5630]=0;
dp[5631]=24;
dp[5632]=0;
dp[5633]=45;
dp[5634]=24;
dp[5635]=78;
dp[5636]=0;
dp[5637]=42;
dp[5638]=21;
dp[5639]=24;
dp[5640]=12;
dp[5641]=39;
dp[5642]=30;
dp[5643]=54;
dp[5644]=30;
dp[5645]=24;
dp[5646]=0;
dp[5647]=84;
dp[5648]=15;
dp[5649]=24;
dp[5650]=24;
dp[5651]=9;
dp[5652]=30;
dp[5653]=54;
dp[5654]=9;
dp[5655]=48;
dp[5656]=6;
dp[5657]=33;
dp[5658]=18;
dp[5659]=57;
dp[5660]=18;
dp[5661]=30;
dp[5662]=0;
dp[5663]=60;
dp[5664]=3;
dp[5665]=54;
dp[5666]=27;
dp[5667]=33;
dp[5668]=30;
dp[5669]=36;
dp[5670]=24;
dp[5671]=42;
dp[5672]=0;
dp[5673]=54;
dp[5674]=18;
dp[5675]=39;
dp[5676]=24;
dp[5677]=54;
dp[5678]=0;
dp[5679]=60;
dp[5680]=18;
dp[5681]=24;
dp[5682]=15;
dp[5683]=75;
dp[5684]=12;
dp[5685]=24;
dp[5686]=12;
dp[5687]=42;
dp[5688]=0;
dp[5689]=39;
dp[5690]=12;
dp[5691]=36;
dp[5692]=36;
dp[5693]=36;
dp[5694]=0;
dp[5695]=30;
dp[5696]=3;
dp[5697]=66;
dp[5698]=42;
dp[5699]=15;
dp[5700]=24;
dp[5701]=72;
dp[5702]=12;
dp[5703]=48;
dp[5704]=12;
dp[5705]=42;
dp[5706]=12;
dp[5707]=48;
dp[5708]=15;
dp[5709]=24;
dp[5710]=0;
dp[5711]=18;
dp[5712]=18;
dp[5713]=60;
dp[5714]=6;
dp[5715]=60;
dp[5716]=18;
dp[5717]=36;
dp[5718]=9;
dp[5719]=24;
dp[5720]=6;
dp[5721]=27;
dp[5722]=36;
dp[5723]=30;
dp[5724]=24;
dp[5725]=90;
dp[5726]=0;
dp[5727]=60;
dp[5728]=3;
dp[5729]=21;
dp[5730]=18;
dp[5731]=54;
dp[5732]=24;
dp[5733]=48;
dp[5734]=18;
dp[5735]=18;
dp[5736]=12;
dp[5737]=51;
dp[5738]=24;
dp[5739]=39;
dp[5740]=18;
dp[5741]=18;
dp[5742]=0;
dp[5743]=72;
dp[5744]=12;
dp[5745]=42;
dp[5746]=21;
dp[5747]=36;
dp[5748]=24;
dp[5749]=36;
dp[5750]=6;
dp[5751]=36;
dp[5752]=0;
dp[5753]=33;
dp[5754]=18;
dp[5755]=42;
dp[5756]=0;
dp[5757]=60;
dp[5758]=0;
dp[5759]=18;
dp[5760]=6;
dp[5761]=42;
dp[5762]=21;
dp[5763]=39;
dp[5764]=39;
dp[5765]=36;
dp[5766]=13;
dp[5767]=84;
dp[5768]=6;
dp[5769]=24;
dp[5770]=18;
dp[5771]=30;
dp[5772]=24;
dp[5773]=78;
dp[5774]=0;
dp[5775]=36;
dp[5776]=3;
dp[5777]=54;
dp[5778]=39;
dp[5779]=51;
dp[5780]=18;
dp[5781]=30;
dp[5782]=21;
dp[5783]=24;
dp[5784]=3;
dp[5785]=60;
dp[5786]=12;
dp[5787]=87;
dp[5788]=42;
dp[5789]=30;
dp[5790]=0;
dp[5791]=36;
dp[5792]=6;
dp[5793]=30;
dp[5794]=15;
dp[5795]=36;
dp[5796]=12;
dp[5797]=54;
dp[5798]=18;
dp[5799]=42;
dp[5800]=12;
dp[5801]=27;
dp[5802]=24;
dp[5803]=84;
dp[5804]=15;
dp[5805]=42;
dp[5806]=0;
dp[5807]=18;
dp[5808]=9;
dp[5809]=54;
dp[5810]=18;
dp[5811]=30;
dp[5812]=30;
dp[5813]=48;
dp[5814]=12;
dp[5815]=72;
dp[5816]=0;
dp[5817]=54;
dp[5818]=42;
dp[5819]=9;
dp[5820]=12;
dp[5821]=36;
dp[5822]=0;
dp[5823]=60;
dp[5824]=0;
dp[5825]=27;
dp[5826]=21;
dp[5827]=78;
dp[5828]=18;
dp[5829]=42;
dp[5830]=30;
dp[5831]=30;
dp[5832]=6;
dp[5833]=54;
dp[5834]=6;
dp[5835]=30;
dp[5836]=18;
dp[5837]=24;
dp[5838]=0;
dp[5839]=60;
dp[5840]=12;
dp[5841]=42;
dp[5842]=36;
dp[5843]=48;
dp[5844]=24;
dp[5845]=54;
dp[5846]=6;
dp[5847]=36;
dp[5848]=15;
dp[5849]=12;
dp[5850]=48;
dp[5851]=21;
dp[5852]=12;
dp[5853]=30;
dp[5854]=0;
dp[5855]=36;
dp[5856]=0;
dp[5857]=102;
dp[5858]=6;
dp[5859]=18;
dp[5860]=12;
dp[5861]=24;
dp[5862]=9;
dp[5863]=60;
dp[5864]=12;
dp[5865]=48;
dp[5866]=24;
dp[5867]=33;
dp[5868]=30;
dp[5869]=66;
dp[5870]=0;
dp[5871]=30;
dp[5872]=12;
dp[5873]=30;
dp[5874]=15;
dp[5875]=60;
dp[5876]=12;
dp[5877]=54;
dp[5878]=36;
dp[5879]=30;
dp[5880]=0;
dp[5881]=36;
dp[5882]=6;
dp[5883]=72;
dp[5884]=18;
dp[5885]=36;
dp[5886]=0;
dp[5887]=54;
dp[5888]=0;
dp[5889]=30;
dp[5890]=36;
dp[5891]=9;
dp[5892]=15;
dp[5893]=60;
dp[5894]=0;
dp[5895]=60;
dp[5896]=15;
dp[5897]=39;
dp[5898]=12;
dp[5899]=63;
dp[5900]=18;
dp[5901]=42;
dp[5902]=0;
dp[5903]=30;
dp[5904]=18;
dp[5905]=60;
dp[5906]=21;
dp[5907]=57;
dp[5908]=30;
dp[5909]=0;
dp[5910]=18;
dp[5911]=54;
dp[5912]=3;
dp[5913]=75;
dp[5914]=30;
dp[5915]=48;
dp[5916]=24;
dp[5917]=42;
dp[5918]=0;
dp[5919]=24;
dp[5920]=12;
dp[5921]=36;
dp[5922]=42;
dp[5923]=57;
dp[5924]=9;
dp[5925]=48;
dp[5926]=9;
dp[5927]=36;
dp[5928]=6;
dp[5929]=45;
dp[5930]=12;
dp[5931]=24;
dp[5932]=48;
dp[5933]=54;
dp[5934]=0;
dp[5935]=66;
dp[5936]=0;
dp[5937]=45;
dp[5938]=33;
dp[5939]=30;
dp[5940]=18;
dp[5941]=54;
dp[5942]=18;
dp[5943]=36;
dp[5944]=0;
dp[5945]=36;
dp[5946]=6;
dp[5947]=54;
dp[5948]=30;
dp[5949]=54;
dp[5950]=0;
dp[5951]=36;
dp[5952]=0;
dp[5953]=66;
dp[5954]=12;
dp[5955]=42;
dp[5956]=21;
dp[5957]=24;
dp[5958]=18;
dp[5959]=48;
dp[5960]=6;
dp[5961]=21;
dp[5962]=48;
dp[5963]=42;
dp[5964]=12;
dp[5965]=60;
dp[5966]=0;
dp[5967]=84;
dp[5968]=12;
dp[5969]=0;
dp[5970]=12;
dp[5971]=54;
dp[5972]=24;
dp[5973]=36;
dp[5974]=18;
dp[5975]=18;
dp[5976]=12;
dp[5977]=81;
dp[5978]=18;
dp[5979]=33;
dp[5980]=18;
dp[5981]=12;
dp[5982]=0;
dp[5983]=66;
dp[5984]=3;
dp[5985]=66;
dp[5986]=6;
dp[5987]=33;
dp[5988]=48;
dp[5989]=48;
dp[5990]=6;
dp[5991]=24;
dp[5992]=24;
dp[5993]=36;
dp[5994]=18;
dp[5995]=60;
dp[5996]=6;
dp[5997]=36;
dp[5998]=0;
dp[5999]=24;
dp[6000]=6;
dp[6001]=39;
dp[6002]=21;
dp[6003]=42;
dp[6004]=18;
dp[6005]=42;
dp[6006]=12;
dp[6007]=60;
dp[6008]=0;
dp[6009]=24;
dp[6010]=30;
dp[6011]=33;
dp[6012]=36;
dp[6013]=72;
dp[6014]=0;
dp[6015]=30;
dp[6016]=0;
dp[6017]=36;
dp[6018]=36;
dp[6019]=42;
dp[6020]=12;
dp[6021]=36;
dp[6022]=15;
dp[6023]=24;
dp[6024]=15;
dp[6025]=75;
dp[6026]=30;
dp[6027]=63;
dp[6028]=27;
dp[6029]=24;
dp[6030]=0;
dp[6031]=42;
dp[6032]=6;
dp[6033]=63;
dp[6034]=30;
dp[6035]=18;
dp[6036]=12;
dp[6037]=108;
dp[6038]=9;
dp[6039]=48;
dp[6040]=12;
dp[6041]=24;
dp[6042]=12;
dp[6043]=72;
dp[6044]=18;
dp[6045]=30;
dp[6046]=0;
dp[6047]=54;
dp[6048]=6;
dp[6049]=30;
dp[6050]=9;
dp[6051]=63;
dp[6052]=27;
dp[6053]=48;
dp[6054]=15;
dp[6055]=36;
dp[6056]=6;
dp[6057]=48;
dp[6058]=36;
dp[6059]=18;
dp[6060]=12;
dp[6061]=54;
dp[6062]=0;
dp[6063]=42;
dp[6064]=9;
dp[6065]=36;
dp[6066]=36;
dp[6067]=63;
dp[6068]=18;
dp[6069]=36;
dp[6070]=24;
dp[6071]=36;
dp[6072]=0;
dp[6073]=75;
dp[6074]=6;
dp[6075]=63;
dp[6076]=24;
dp[6077]=36;
dp[6078]=0;
dp[6079]=48;
dp[6080]=6;
dp[6081]=27;
dp[6082]=39;
dp[6083]=30;
dp[6084]=18;
dp[6085]=30;
dp[6086]=9;
dp[6087]=54;
dp[6088]=18;
dp[6089]=36;
dp[6090]=18;
dp[6091]=39;
dp[6092]=21;
dp[6093]=66;
dp[6094]=0;
dp[6095]=30;
dp[6096]=0;
dp[6097]=54;
dp[6098]=18;
dp[6099]=42;
dp[6100]=36;
dp[6101]=12;
dp[6102]=24;
dp[6103]=108;
dp[6104]=0;
dp[6105]=30;
dp[6106]=24;
dp[6107]=42;
dp[6108]=12;
dp[6109]=48;
dp[6110]=0;
dp[6111]=24;
dp[6112]=0;
dp[6113]=15;
dp[6114]=9;
dp[6115]=48;
dp[6116]=18;
dp[6117]=66;
dp[6118]=24;
dp[6119]=24;
dp[6120]=12;
dp[6121]=54;
dp[6122]=12;
dp[6123]=36;
dp[6124]=21;
dp[6125]=54;
dp[6126]=0;
dp[6127]=54;
dp[6128]=18;
dp[6129]=45;
dp[6130]=42;
dp[6131]=36;
dp[6132]=24;
dp[6133]=42;
dp[6134]=3;
dp[6135]=36;
dp[6136]=0;
dp[6137]=42;
dp[6138]=48;
dp[6139]=42;
dp[6140]=12;
dp[6141]=36;
dp[6142]=0;
dp[6143]=36;
dp[6144]=1;
dp[6145]=60;
dp[6146]=18;
dp[6147]=36;
dp[6148]=18;
dp[6149]=36;
dp[6150]=15;
dp[6151]=54;
dp[6152]=9;
dp[6153]=60;
dp[6154]=30;
dp[6155]=24;
dp[6156]=21;
dp[6157]=48;
dp[6158]=0;
dp[6159]=24;
dp[6160]=18;
dp[6161]=24;
dp[6162]=18;
dp[6163]=90;
dp[6164]=6;
dp[6165]=72;
dp[6166]=15;
dp[6167]=36;
dp[6168]=9;
dp[6169]=48;
dp[6170]=6;
dp[6171]=36;
dp[6172]=42;
dp[6173]=48;
dp[6174]=0;
dp[6175]=78;
dp[6176]=3;
dp[6177]=54;
dp[6178]=27;
dp[6179]=18;
dp[6180]=36;
dp[6181]=48;
dp[6182]=15;
dp[6183]=54;
dp[6184]=12;
dp[6185]=30;
dp[6186]=24;
dp[6187]=84;
dp[6188]=12;
dp[6189]=18;
dp[6190]=0;
dp[6191]=18;
dp[6192]=12;
dp[6193]=105;
dp[6194]=12;
dp[6195]=24;
dp[6196]=30;
dp[6197]=30;
dp[6198]=18;
dp[6199]=36;
dp[6200]=0;
dp[6201]=60;
dp[6202]=30;
dp[6203]=27;
dp[6204]=12;
dp[6205]=48;
dp[6206]=0;
dp[6207]=90;
dp[6208]=6;
dp[6209]=18;
dp[6210]=18;
dp[6211]=33;
dp[6212]=21;
dp[6213]=42;
dp[6214]=24;
dp[6215]=24;
dp[6216]=12;
dp[6217]=45;
dp[6218]=24;
dp[6219]=60;
dp[6220]=36;
dp[6221]=36;
dp[6222]=0;
dp[6223]=66;
dp[6224]=6;
dp[6225]=27;
dp[6226]=15;
dp[6227]=42;
dp[6228]=24;
dp[6229]=60;
dp[6230]=12;
dp[6231]=18;
dp[6232]=9;
dp[6233]=30;
dp[6234]=18;
dp[6235]=84;
dp[6236]=12;
dp[6237]=72;
dp[6238]=0;
dp[6239]=12;
dp[6240]=6;
dp[6241]=42;
dp[6242]=21;
dp[6243]=45;
dp[6244]=12;
dp[6245]=18;
dp[6246]=9;
dp[6247]=96;
dp[6248]=12;
dp[6249]=21;
dp[6250]=30;
dp[6251]=30;
dp[6252]=24;
dp[6253]=66;
dp[6254]=0;
dp[6255]=48;
dp[6256]=12;
dp[6257]=42;
dp[6258]=18;
dp[6259]=36;
dp[6260]=18;
dp[6261]=24;
dp[6262]=24;
dp[6263]=24;
dp[6264]=0;
dp[6265]=30;
dp[6266]=12;
dp[6267]=27;
dp[6268]=42;
dp[6269]=18;
dp[6270]=0;
dp[6271]=72;
dp[6272]=0;
dp[6273]=84;
dp[6274]=27;
dp[6275]=54;
dp[6276]=15;
dp[6277]=102;
dp[6278]=12;
dp[6279]=36;
dp[6280]=6;
dp[6281]=39;
dp[6282]=36;
dp[6283]=36;
dp[6284]=15;
dp[6285]=36;
dp[6286]=0;
dp[6287]=30;
dp[6288]=15;
dp[6289]=57;
dp[6290]=12;
dp[6291]=57;
dp[6292]=42;
dp[6293]=30;
dp[6294]=9;
dp[6295]=60;
dp[6296]=6;
dp[6297]=27;
dp[6298]=42;
dp[6299]=27;
dp[6300]=30;
dp[6301]=36;
dp[6302]=0;
dp[6303]=54;
dp[6304]=6;
dp[6305]=24;
dp[6306]=21;
dp[6307]=78;
dp[6308]=12;
dp[6309]=42;
dp[6310]=18;
dp[6311]=18;
dp[6312]=12;
dp[6313]=84;
dp[6314]=18;
dp[6315]=54;
dp[6316]=18;
dp[6317]=48;
dp[6318]=0;
dp[6319]=66;
dp[6320]=12;
dp[6321]=15;
dp[6322]=36;
dp[6323]=30;
dp[6324]=18;
dp[6325]=72;
dp[6326]=9;
dp[6327]=66;
dp[6328]=0;
dp[6329]=27;
dp[6330]=18;
dp[6331]=24;
dp[6332]=6;
dp[6333]=78;
dp[6334]=0;
dp[6335]=42;
dp[6336]=6;
dp[6337]=81;
dp[6338]=27;
dp[6339]=27;
dp[6340]=36;
dp[6341]=24;
dp[6342]=24;
dp[6343]=48;
dp[6344]=0;
dp[6345]=72;
dp[6346]=18;
dp[6347]=39;
dp[6348]=30;
dp[6349]=42;
dp[6350]=0;
dp[6351]=18;
dp[6352]=18;
dp[6353]=30;
dp[6354]=24;
dp[6355]=78;
dp[6356]=6;
dp[6357]=18;
dp[6358]=18;
dp[6359]=36;
dp[6360]=0;
dp[6361]=48;
dp[6362]=30;
dp[6363]=84;
dp[6364]=6;
dp[6365]=18;
dp[6366]=0;
dp[6367]=54;
dp[6368]=0;
dp[6369]=42;
dp[6370]=36;
dp[6371]=12;
dp[6372]=30;
dp[6373]=90;
dp[6374]=12;
dp[6375]=48;
dp[6376]=18;
dp[6377]=24;
dp[6378]=18;
dp[6379]=21;
dp[6380]=18;
dp[6381]=48;
dp[6382]=0;
dp[6383]=60;
dp[6384]=0;
dp[6385]=60;
dp[6386]=6;
dp[6387]=30;
dp[6388]=42;
dp[6389]=24;
dp[6390]=18;
dp[6391]=66;
dp[6392]=0;
dp[6393]=27;
dp[6394]=36;
dp[6395]=24;
dp[6396]=18;
dp[6397]=54;
dp[6398]=0;
dp[6399]=48;
dp[6400]=6;
dp[6401]=30;
dp[6402]=18;
dp[6403]=90;
dp[6404]=15;
dp[6405]=42;
dp[6406]=9;
dp[6407]=48;
dp[6408]=18;
dp[6409]=42;
dp[6410]=6;
dp[6411]=45;
dp[6412]=24;
dp[6413]=36;
dp[6414]=0;
dp[6415]=48;
dp[6416]=0;
dp[6417]=78;
dp[6418]=39;
dp[6419]=27;
dp[6420]=12;
dp[6421]=42;
dp[6422]=27;
dp[6423]=48;
dp[6424]=6;
dp[6425]=45;
dp[6426]=18;
dp[6427]=72;
dp[6428]=36;
dp[6429]=48;
dp[6430]=0;
dp[6431]=18;
dp[6432]=9;
dp[6433]=66;
dp[6434]=9;
dp[6435]=54;
dp[6436]=33;
dp[6437]=18;
dp[6438]=18;
dp[6439]=66;
dp[6440]=12;
dp[6441]=39;
dp[6442]=36;
dp[6443]=45;
dp[6444]=12;
dp[6445]=72;
dp[6446]=0;
dp[6447]=48;
dp[6448]=12;
dp[6449]=21;
dp[6450]=39;
dp[6451]=33;
dp[6452]=18;
dp[6453]=60;
dp[6454]=18;
dp[6455]=36;
dp[6456]=0;
dp[6457]=78;
dp[6458]=18;
dp[6459]=39;
dp[6460]=36;
dp[6461]=24;
dp[6462]=0;
dp[6463]=30;
dp[6464]=0;
dp[6465]=30;
dp[6466]=30;
dp[6467]=54;
dp[6468]=21;
dp[6469]=66;
dp[6470]=6;
dp[6471]=30;
dp[6472]=21;
dp[6473]=39;
dp[6474]=18;
dp[6475]=60;
dp[6476]=15;
dp[6477]=72;
dp[6478]=0;
dp[6479]=30;
dp[6480]=18;
dp[6481]=45;
dp[6482]=12;
dp[6483]=39;
dp[6484]=18;
dp[6485]=60;
dp[6486]=6;
dp[6487]=66;
dp[6488]=15;
dp[6489]=36;
dp[6490]=30;
dp[6491]=12;
dp[6492]=18;
dp[6493]=60;
dp[6494]=0;
dp[6495]=60;
dp[6496]=0;
dp[6497]=18;
dp[6498]=33;
dp[6499]=57;
dp[6500]=18;
dp[6501]=24;
dp[6502]=24;
dp[6503]=42;
dp[6504]=6;
dp[6505]=66;
dp[6506]=12;
dp[6507]=81;
dp[6508]=42;
dp[6509]=18;
dp[6510]=0;
dp[6511]=36;
dp[6512]=6;
dp[6513]=42;
dp[6514]=18;
dp[6515]=24;
dp[6516]=24;
dp[6517]=72;
dp[6518]=0;
dp[6519]=18;
dp[6520]=0;
dp[6521]=30;
dp[6522]=30;
dp[6523]=87;
dp[6524]=18;
dp[6525]=36;
dp[6526]=0;
dp[6527]=42;
dp[6528]=3;
dp[6529]=45;
dp[6530]=12;
dp[6531]=36;
dp[6532]=42;
dp[6533]=24;
dp[6534]=25;
dp[6535]=30;
dp[6536]=6;
dp[6537]=72;
dp[6538]=24;
dp[6539]=18;
dp[6540]=18;
dp[6541]=60;
dp[6542]=0;
dp[6543]=102;
dp[6544]=12;
dp[6545]=42;
dp[6546]=12;
dp[6547]=90;
dp[6548]=12;
dp[6549]=24;
dp[6550]=27;
dp[6551]=24;
dp[6552]=12;
dp[6553]=69;
dp[6554]=24;
dp[6555]=30;
dp[6556]=18;
dp[6557]=42;
dp[6558]=0;
dp[6559]=48;
dp[6560]=0;
dp[6561]=42;
dp[6562]=45;
dp[6563]=39;
dp[6564]=15;
dp[6565]=60;
dp[6566]=18;
dp[6567]=30;
dp[6568]=12;
dp[6569]=33;
dp[6570]=24;
dp[6571]=72;
dp[6572]=18;
dp[6573]=36;
dp[6574]=0;
dp[6575]=24;
dp[6576]=12;
dp[6577]=51;
dp[6578]=24;
dp[6579]=39;
dp[6580]=36;
dp[6581]=24;
dp[6582]=6;
dp[6583]=120;
dp[6584]=0;
dp[6585]=72;
dp[6586]=24;
dp[6587]=30;
dp[6588]=30;
dp[6589]=30;
dp[6590]=0;
dp[6591]=24;
dp[6592]=12;
dp[6593]=72;
dp[6594]=18;
dp[6595]=54;
dp[6596]=3;
dp[6597]=84;
dp[6598]=30;
dp[6599]=30;
dp[6600]=21;
dp[6601]=42;
dp[6602]=24;
dp[6603]=30;
dp[6604]=18;
dp[6605]=30;
dp[6606]=0;
dp[6607]=54;
dp[6608]=0;
dp[6609]=36;
dp[6610]=30;
dp[6611]=24;
dp[6612]=30;
dp[6613]=72;
dp[6614]=9;
dp[6615]=72;
dp[6616]=6;
dp[6617]=30;
dp[6618]=24;
dp[6619]=36;
dp[6620]=24;
dp[6621]=30;
dp[6622]=0;
dp[6623]=30;
dp[6624]=0;
dp[6625]=90;
dp[6626]=12;
dp[6627]=48;
dp[6628]=27;
dp[6629]=24;
dp[6630]=6;
dp[6631]=54;
dp[6632]=12;
dp[6633]=39;
dp[6634]=36;
dp[6635]=18;
dp[6636]=18;
dp[6637]=78;
dp[6638]=0;
dp[6639]=36;
dp[6640]=12;
dp[6641]=18;
dp[6642]=39;
dp[6643]=66;
dp[6644]=6;
dp[6645]=54;
dp[6646]=18;
dp[6647]=36;
dp[6648]=0;
dp[6649]=54;
dp[6650]=18;
dp[6651]=42;
dp[6652]=12;
dp[6653]=30;
dp[6654]=0;
dp[6655]=78;
dp[6656]=0;
dp[6657]=48;
dp[6658]=45;
dp[6659]=27;
dp[6660]=36;
dp[6661]=36;
dp[6662]=9;
dp[6663]=54;
dp[6664]=15;
dp[6665]=6;
dp[6666]=12;
dp[6667]=99;
dp[6668]=15;
dp[6669]=48;
dp[6670]=0;
dp[6671]=24;
dp[6672]=3;
dp[6673]=60;
dp[6674]=12;
dp[6675]=45;
dp[6676]=36;
dp[6677]=36;
dp[6678]=30;
dp[6679]=24;
dp[6680]=12;
dp[6681]=57;
dp[6682]=30;
dp[6683]=42;
dp[6684]=18;
dp[6685]=54;
dp[6686]=0;
dp[6687]=36;
dp[6688]=6;
dp[6689]=45;
dp[6690]=24;
dp[6691]=63;
dp[6692]=30;
dp[6693]=60;
dp[6694]=12;
dp[6695]=42;
dp[6696]=6;
dp[6697]=102;
dp[6698]=18;
dp[6699]=30;
dp[6700]=33;
dp[6701]=18;
dp[6702]=0;
dp[6703]=84;
dp[6704]=12;
dp[6705]=54;
dp[6706]=24;
dp[6707]=39;
dp[6708]=12;
dp[6709]=42;
dp[6710]=0;
dp[6711]=36;
dp[6712]=0;
dp[6713]=54;
dp[6714]=24;
dp[6715]=60;
dp[6716]=12;
dp[6717]=42;
dp[6718]=0;
dp[6719]=48;
dp[6720]=6;
dp[6721]=30;
dp[6722]=9;
dp[6723]=93;
dp[6724]=24;
dp[6725]=18;
dp[6726]=21;
dp[6727]=60;
dp[6728]=6;
dp[6729]=21;
dp[6730]=36;
dp[6731]=18;
dp[6732]=54;
dp[6733]=102;
dp[6734]=0;
dp[6735]=30;
dp[6736]=18;
dp[6737]=36;
dp[6738]=21;
dp[6739]=48;
dp[6740]=12;
dp[6741]=30;
dp[6742]=27;
dp[6743]=42;
dp[6744]=3;
dp[6745]=54;
dp[6746]=12;
dp[6747]=66;
dp[6748]=36;
dp[6749]=36;
dp[6750]=0;
dp[6751]=48;
dp[6752]=9;
dp[6753]=45;
dp[6754]=33;
dp[6755]=30;
dp[6756]=9;
dp[6757]=84;
dp[6758]=18;
dp[6759]=30;
dp[6760]=12;
dp[6761]=33;
dp[6762]=36;
dp[6763]=51;
dp[6764]=12;
dp[6765]=54;
dp[6766]=0;
dp[6767]=36;
dp[6768]=18;
dp[6769]=42;
dp[6770]=12;
dp[6771]=30;
dp[6772]=36;
dp[6773]=24;
dp[6774]=9;
dp[6775]=72;
dp[6776]=0;
dp[6777]=48;
dp[6778]=30;
dp[6779]=36;
dp[6780]=6;
dp[6781]=78;
dp[6782]=0;
dp[6783]=42;
dp[6784]=0;
dp[6785]=18;
dp[6786]=24;
dp[6787]=63;
dp[6788]=21;
dp[6789]=36;
dp[6790]=18;
dp[6791]=24;
dp[6792]=15;
dp[6793]=66;
dp[6794]=0;
dp[6795]=42;
dp[6796]=27;
dp[6797]=54;
dp[6798]=0;
dp[6799]=30;
dp[6800]=9;
dp[6801]=51;
dp[6802]=45;
dp[6803]=45;
dp[6804]=24;
dp[6805]=48;
dp[6806]=12;
dp[6807]=72;
dp[6808]=12;
dp[6809]=33;
dp[6810]=24;
dp[6811]=39;
dp[6812]=30;
dp[6813]=66;
dp[6814]=0;
dp[6815]=18;
dp[6816]=6;
dp[6817]=69;
dp[6818]=12;
dp[6819]=36;
dp[6820]=24;
dp[6821]=36;
dp[6822]=18;
dp[6823]=90;
dp[6824]=6;
dp[6825]=60;
dp[6826]=24;
dp[6827]=36;
dp[6828]=27;
dp[6829]=36;
dp[6830]=0;
dp[6831]=60;
dp[6832]=18;
dp[6833]=33;
dp[6834]=21;
dp[6835]=84;
dp[6836]=12;
dp[6837]=36;
dp[6838]=30;
dp[6839]=18;
dp[6840]=0;
dp[6841]=33;
dp[6842]=24;
dp[6843]=51;
dp[6844]=30;
dp[6845]=24;
dp[6846]=0;
dp[6847]=84;
dp[6848]=0;
dp[6849]=57;
dp[6850]=33;
dp[6851]=36;
dp[6852]=21;
dp[6853]=84;
dp[6854]=12;
dp[6855]=30;
dp[6856]=12;
dp[6857]=33;
dp[6858]=36;
dp[6859]=63;
dp[6860]=18;
dp[6861]=24;
dp[6862]=0;
dp[6863]=30;
dp[6864]=6;
dp[6865]=90;
dp[6866]=21;
dp[6867]=66;
dp[6868]=30;
dp[6869]=30;
dp[6870]=24;
dp[6871]=36;
dp[6872]=0;
dp[6873]=54;
dp[6874]=12;
dp[6875]=51;
dp[6876]=18;
dp[6877]=78;
dp[6878]=0;
dp[6879]=36;
dp[6880]=0;
dp[6881]=18;
dp[6882]=18;
dp[6883]=54;
dp[6884]=21;
dp[6885]=48;
dp[6886]=12;
dp[6887]=66;
dp[6888]=18;
dp[6889]=21;
dp[6890]=18;
dp[6891]=33;
dp[6892]=21;
dp[6893]=42;
dp[6894]=0;
dp[6895]=66;
dp[6896]=6;
dp[6897]=48;
dp[6898]=54;
dp[6899]=21;
dp[6900]=30;
dp[6901]=66;
dp[6902]=12;
dp[6903]=66;
dp[6904]=0;
dp[6905]=24;
dp[6906]=24;
dp[6907]=63;
dp[6908]=24;
dp[6909]=36;
dp[6910]=0;
dp[6911]=42;
dp[6912]=3;
dp[6913]=60;
dp[6914]=18;
dp[6915]=30;
dp[6916]=6;
dp[6917]=36;
dp[6918]=9;
dp[6919]=54;
dp[6920]=6;
dp[6921]=72;
dp[6922]=48;
dp[6923]=36;
dp[6924]=15;
dp[6925]=54;
dp[6926]=0;
dp[6927]=30;
dp[6928]=27;
dp[6929]=12;
dp[6930]=18;
dp[6931]=60;
dp[6932]=12;
dp[6933]=66;
dp[6934]=15;
dp[6935]=48;
dp[6936]=10;
dp[6937]=84;
dp[6938]=12;
dp[6939]=39;
dp[6940]=42;
dp[6941]=12;
dp[6942]=0;
dp[6943]=66;
dp[6944]=6;
dp[6945]=24;
dp[6946]=18;
dp[6947]=21;
dp[6948]=36;
dp[6949]=54;
dp[6950]=24;
dp[6951]=24;
dp[6952]=12;
dp[6953]=51;
dp[6954]=18;
dp[6955]=66;
dp[6956]=12;
dp[6957]=90;
dp[6958]=0;
dp[6959]=18;
dp[6960]=6;
dp[6961]=87;
dp[6962]=15;
dp[6963]=75;
dp[6964]=24;
dp[6965]=30;
dp[6966]=15;
dp[6967]=60;
dp[6968]=0;
dp[6969]=24;
dp[6970]=42;
dp[6971]=24;
dp[6972]=24;
dp[6973]=48;
dp[6974]=0;
dp[6975]=84;
dp[6976]=6;
dp[6977]=51;
dp[6978]=39;
dp[6979]=60;
dp[6980]=12;
dp[6981]=18;
dp[6982]=30;
dp[6983]=36;
dp[6984]=12;
dp[6985]=60;
dp[6986]=12;
dp[6987]=60;
dp[6988]=48;
dp[6989]=36;
dp[6990]=0;
dp[6991]=54;
dp[6992]=6;
dp[6993]=42;
dp[6994]=12;
dp[6995]=6;
dp[6996]=18;
dp[6997]=78;
dp[6998]=6;
dp[6999]=48;
dp[7000]=12;
dp[7001]=12;
dp[7002]=36;
dp[7003]=84;
dp[7004]=0;
dp[7005]=48;
dp[7006]=0;
dp[7007]=54;
dp[7008]=3;
dp[7009]=48;
dp[7010]=18;
dp[7011]=45;
dp[7012]=51;
dp[7013]=54;
dp[7014]=6;
dp[7015]=72;
dp[7016]=6;
dp[7017]=51;
dp[7018]=30;
dp[7019]=45;
dp[7020]=30;
dp[7021]=48;
dp[7022]=0;
dp[7023]=36;
dp[7024]=6;
dp[7025]=36;
dp[7026]=15;
dp[7027]=78;
dp[7028]=24;
dp[7029]=42;
dp[7030]=24;
dp[7031]=24;
dp[7032]=0;
dp[7033]=90;
dp[7034]=18;
dp[7035]=36;
dp[7036]=24;
dp[7037]=24;
dp[7038]=0;
dp[7039]=36;
dp[7040]=0;
dp[7041]=36;
dp[7042]=30;
dp[7043]=30;
dp[7044]=30;
dp[7045]=66;
dp[7046]=6;
dp[7047]=78;
dp[7048]=21;
dp[7049]=30;
dp[7050]=12;
dp[7051]=21;
dp[7052]=15;
dp[7053]=60;
dp[7054]=0;
dp[7055]=36;
dp[7056]=12;
dp[7057]=66;
dp[7058]=21;
dp[7059]=36;
dp[7060]=24;
dp[7061]=30;
dp[7062]=18;
dp[7063]=60;
dp[7064]=9;
dp[7065]=54;
dp[7066]=48;
dp[7067]=24;
dp[7068]=18;
dp[7069]=48;
dp[7070]=0;
dp[7071]=30;
dp[7072]=6;
dp[7073]=42;
dp[7074]=18;
dp[7075]=81;
dp[7076]=18;
dp[7077]=54;
dp[7078]=27;
dp[7079]=24;
dp[7080]=12;
dp[7081]=30;
dp[7082]=18;
dp[7083]=84;
dp[7084]=30;
dp[7085]=24;
dp[7086]=0;
dp[7087]=102;
dp[7088]=9;
dp[7089]=42;
dp[7090]=42;
dp[7091]=36;
dp[7092]=24;
dp[7093]=90;
dp[7094]=3;
dp[7095]=30;
dp[7096]=0;
dp[7097]=60;
dp[7098]=30;
dp[7099]=42;
dp[7100]=18;
dp[7101]=24;
dp[7102]=0;
dp[7103]=18;
dp[7104]=0;
dp[7105]=78;
dp[7106]=12;
dp[7107]=42;
dp[7108]=27;
dp[7109]=42;
dp[7110]=18;
dp[7111]=66;
dp[7112]=18;
dp[7113]=45;
dp[7114]=18;
dp[7115]=42;
dp[7116]=9;
dp[7117]=84;
dp[7118]=0;
dp[7119]=54;
dp[7120]=6;
dp[7121]=15;
dp[7122]=54;
dp[7123]=63;
dp[7124]=18;
dp[7125]=54;
dp[7126]=24;
dp[7127]=24;
dp[7128]=9;
dp[7129]=57;
dp[7130]=24;
dp[7131]=45;
dp[7132]=54;
dp[7133]=36;
dp[7134]=0;
dp[7135]=60;
dp[7136]=0;
dp[7137]=66;
dp[7138]=27;
dp[7139]=33;
dp[7140]=18;
dp[7141]=30;
dp[7142]=9;
dp[7143]=60;
dp[7144]=24;
dp[7145]=30;
dp[7146]=12;
dp[7147]=54;
dp[7148]=21;
dp[7149]=24;
dp[7150]=0;
dp[7151]=12;
dp[7152]=18;
dp[7153]=108;
dp[7154]=15;
dp[7155]=66;
dp[7156]=12;
dp[7157]=30;
dp[7158]=27;
dp[7159]=66;
dp[7160]=0;
dp[7161]=36;
dp[7162]=30;
dp[7163]=36;
dp[7164]=24;
dp[7165]=66;
dp[7166]=0;
dp[7167]=60;
dp[7168]=0;
dp[7169]=9;
dp[7170]=24;
dp[7171]=54;
dp[7172]=12;
dp[7173]=90;
dp[7174]=15;
dp[7175]=42;
dp[7176]=0;
dp[7177]=51;
dp[7178]=30;
dp[7179]=18;
dp[7180]=30;
dp[7181]=48;
dp[7182]=0;
dp[7183]=84;
dp[7184]=9;
dp[7185]=48;
dp[7186]=21;
dp[7187]=54;
dp[7188]=30;
dp[7189]=24;
dp[7190]=18;
dp[7191]=36;
dp[7192]=12;
dp[7193]=45;
dp[7194]=18;
dp[7195]=96;
dp[7196]=6;
dp[7197]=30;
dp[7198]=0;
dp[7199]=30;
dp[7200]=9;
dp[7201]=30;
dp[7202]=24;
dp[7203]=42;
dp[7204]=24;
dp[7205]=24;
dp[7206]=15;
dp[7207]=66;
dp[7208]=6;
dp[7209]=69;
dp[7210]=36;
dp[7211]=15;
dp[7212]=15;
dp[7213]=84;
dp[7214]=0;
dp[7215]=36;
dp[7216]=15;
dp[7217]=48;
dp[7218]=27;
dp[7219]=45;
dp[7220]=18;
dp[7221]=42;
dp[7222]=30;
dp[7223]=36;
dp[7224]=0;
dp[7225]=66;
dp[7226]=6;
dp[7227]=72;
dp[7228]=30;
dp[7229]=48;
dp[7230]=0;
dp[7231]=42;
dp[7232]=3;
dp[7233]=51;
dp[7234]=39;
dp[7235]=30;
dp[7236]=33;
dp[7237]=78;
dp[7238]=12;
dp[7239]=24;
dp[7240]=18;
dp[7241]=30;
dp[7242]=18;
dp[7243]=105;
dp[7244]=21;
dp[7245]=72;
dp[7246]=0;
dp[7247]=42;
dp[7248]=12;
dp[7249]=39;
dp[7250]=18;
dp[7251]=27;
dp[7252]=42;
dp[7253]=24;
dp[7254]=6;
dp[7255]=66;
dp[7256]=3;
dp[7257]=60;
dp[7258]=42;
dp[7259]=30;
dp[7260]=30;
dp[7261]=60;
dp[7262]=0;
dp[7263]=54;
dp[7264]=6;
dp[7265]=54;
dp[7266]=24;
dp[7267]=57;
dp[7268]=6;
dp[7269]=54;
dp[7270]=6;
dp[7271]=24;
dp[7272]=24;
dp[7273]=54;
dp[7274]=12;
dp[7275]=57;
dp[7276]=27;
dp[7277]=42;
dp[7278]=0;
dp[7279]=48;
dp[7280]=6;
dp[7281]=36;
dp[7282]=27;
dp[7283]=57;
dp[7284]=12;
dp[7285]=84;
dp[7286]=12;
dp[7287]=60;
dp[7288]=0;
dp[7289]=12;
dp[7290]=30;
dp[7291]=54;
dp[7292]=24;
dp[7293]=48;
dp[7294]=0;
dp[7295]=18;
dp[7296]=3;
dp[7297]=105;
dp[7298]=36;
dp[7299]=48;
dp[7300]=42;
dp[7301]=24;
dp[7302]=18;
dp[7303]=48;
dp[7304]=6;
dp[7305]=30;
dp[7306]=36;
dp[7307]=45;
dp[7308]=42;
dp[7309]=42;
dp[7310]=0;
dp[7311]=54;
dp[7312]=9;
dp[7313]=36;
dp[7314]=12;
dp[7315]=48;
dp[7316]=12;
dp[7317]=54;
dp[7318]=30;
dp[7319]=30;
dp[7320]=6;
dp[7321]=48;
dp[7322]=6;
dp[7323]=51;
dp[7324]=18;
dp[7325]=36;
dp[7326]=0;
dp[7327]=102;
dp[7328]=6;
dp[7329]=18;
dp[7330]=30;
dp[7331]=33;
dp[7332]=24;
dp[7333]=48;
dp[7334]=18;
dp[7335]=60;
dp[7336]=12;
dp[7337]=60;
dp[7338]=30;
dp[7339]=45;
dp[7340]=12;
dp[7341]=36;
dp[7342]=0;
dp[7343]=54;
dp[7344]=12;
dp[7345]=60;
dp[7346]=6;
dp[7347]=48;
dp[7348]=54;
dp[7349]=12;
dp[7350]=13;
dp[7351]=60;
dp[7352]=0;
dp[7353]=72;
dp[7354]=18;
dp[7355]=24;
dp[7356]=6;
dp[7357]=90;
dp[7358]=0;
dp[7359]=48;
dp[7360]=12;
dp[7361]=15;
dp[7362]=42;
dp[7363]=96;
dp[7364]=18;
dp[7365]=36;
dp[7366]=18;
dp[7367]=36;
dp[7368]=6;
dp[7369]=78;
dp[7370]=24;
dp[7371]=48;
dp[7372]=18;
dp[7373]=30;
dp[7374]=0;
dp[7375]=48;
dp[7376]=18;
dp[7377]=78;
dp[7378]=42;
dp[7379]=24;
dp[7380]=30;
dp[7381]=60;
dp[7382]=6;
dp[7383]=60;
dp[7384]=12;
dp[7385]=18;
dp[7386]=12;
dp[7387]=42;
dp[7388]=30;
dp[7389]=42;
dp[7390]=0;
dp[7391]=24;
dp[7392]=0;
dp[7393]=81;
dp[7394]=9;
dp[7395]=54;
dp[7396]=18;
dp[7397]=60;
dp[7398]=33;
dp[7399]=48;
dp[7400]=0;
dp[7401]=27;
dp[7402]=54;
dp[7403]=51;
dp[7404]=27;
dp[7405]=90;
dp[7406]=0;
dp[7407]=60;
dp[7408]=18;
dp[7409]=24;
dp[7410]=18;
dp[7411]=54;
dp[7412]=24;
dp[7413]=36;
dp[7414]=12;
dp[7415]=42;
dp[7416]=0;
dp[7417]=87;
dp[7418]=24;
dp[7419]=33;
dp[7420]=18;
dp[7421]=24;
dp[7422]=0;
dp[7423]=96;
dp[7424]=0;
dp[7425]=87;
dp[7426]=36;
dp[7427]=30;
dp[7428]=15;
dp[7429]=42;
dp[7430]=12;
dp[7431]=36;
dp[7432]=24;
dp[7433]=24;
dp[7434]=36;
dp[7435]=42;
dp[7436]=21;
dp[7437]=48;
dp[7438]=0;
dp[7439]=30;
dp[7440]=6;
dp[7441]=42;
dp[7442]=18;
dp[7443]=48;
dp[7444]=24;
dp[7445]=24;
dp[7446]=18;
dp[7447]=84;
dp[7448]=3;
dp[7449]=36;
dp[7450]=42;
dp[7451]=42;
dp[7452]=36;
dp[7453]=72;
dp[7454]=0;
dp[7455]=54;
dp[7456]=6;
dp[7457]=30;
dp[7458]=15;
dp[7459]=60;
dp[7460]=6;
dp[7461]=78;
dp[7462]=30;
dp[7463]=24;
dp[7464]=6;
dp[7465]=72;
dp[7466]=6;
dp[7467]=66;
dp[7468]=45;
dp[7469]=24;
dp[7470]=0;
dp[7471]=42;
dp[7472]=21;
dp[7473]=36;
dp[7474]=30;
dp[7475]=36;
dp[7476]=18;
dp[7477]=48;
dp[7478]=12;
dp[7479]=30;
dp[7480]=0;
dp[7481]=39;
dp[7482]=24;
dp[7483]=102;
dp[7484]=18;
dp[7485]=36;
dp[7486]=0;
dp[7487]=12;
dp[7488]=6;
dp[7489]=54;
dp[7490]=6;
dp[7491]=30;
dp[7492]=33;
dp[7493]=66;
dp[7494]=21;
dp[7495]=90;
dp[7496]=3;
dp[7497]=78;
dp[7498]=36;
dp[7499]=9;
dp[7500]=18;
dp[7501]=36;
dp[7502]=0;
dp[7503]=84;
dp[7504]=0;
dp[7505]=30;
dp[7506]=30;
dp[7507]=93;
dp[7508]=24;
dp[7509]=30;
dp[7510]=24;
dp[7511]=30;
dp[7512]=15;
dp[7513]=63;
dp[7514]=12;
dp[7515]=48;
dp[7516]=30;
dp[7517]=54;
dp[7518]=0;
dp[7519]=48;
dp[7520]=0;
dp[7521]=54;
dp[7522]=42;
dp[7523]=42;
dp[7524]=30;
dp[7525]=78;
dp[7526]=0;
dp[7527]=36;
dp[7528]=24;
dp[7529]=39;
dp[7530]=24;
dp[7531]=60;
dp[7532]=12;
dp[7533]=78;
dp[7534]=0;
dp[7535]=60;
dp[7536]=6;
dp[7537]=51;
dp[7538]=30;
dp[7539]=36;
dp[7540]=36;
dp[7541]=30;
dp[7542]=18;
dp[7543]=60;
dp[7544]=0;
dp[7545]=30;
dp[7546]=30;
dp[7547]=51;
dp[7548]=24;
dp[7549]=60;
dp[7550]=0;
dp[7551]=42;
dp[7552]=3;
dp[7553]=24;
dp[7554]=9;
dp[7555]=54;
dp[7556]=21;
dp[7557]=24;
dp[7558]=33;
dp[7559]=30;
dp[7560]=24;
dp[7561]=66;
dp[7562]=24;
dp[7563]=69;
dp[7564]=18;
dp[7565]=30;
dp[7566]=0;
dp[7567]=102;
dp[7568]=15;
dp[7569]=54;
dp[7570]=24;
dp[7571]=15;
dp[7572]=30;
dp[7573]=120;
dp[7574]=6;
dp[7575]=30;
dp[7576]=3;
dp[7577]=51;
dp[7578]=24;
dp[7579]=54;
dp[7580]=12;
dp[7581]=30;
dp[7582]=0;
dp[7583]=36;
dp[7584]=6;
dp[7585]=36;
dp[7586]=12;
dp[7587]=90;
dp[7588]=42;
dp[7589]=12;
dp[7590]=12;
dp[7591]=60;
dp[7592]=12;
dp[7593]=60;
dp[7594]=24;
dp[7595]=42;
dp[7596]=12;
dp[7597]=90;
dp[7598]=0;
dp[7599]=24;
dp[7600]=12;
dp[7601]=42;
dp[7602]=30;
dp[7603]=30;
dp[7604]=6;
dp[7605]=78;
dp[7606]=21;
dp[7607]=42;
dp[7608]=0;
dp[7609]=54;
dp[7610]=24;
dp[7611]=27;
dp[7612]=54;
dp[7613]=24;
dp[7614]=0;
dp[7615]=66;
dp[7616]=6;
dp[7617]=45;
dp[7618]=30;
dp[7619]=12;
dp[7620]=30;
dp[7621]=42;
dp[7622]=12;
dp[7623]=84;
dp[7624]=15;
dp[7625]=36;
dp[7626]=18;
dp[7627]=84;
dp[7628]=24;
dp[7629]=36;
dp[7630]=0;
dp[7631]=30;
dp[7632]=18;
dp[7633]=72;
dp[7634]=18;
dp[7635]=60;
dp[7636]=24;
dp[7637]=48;
dp[7638]=12;
dp[7639]=54;
dp[7640]=6;
dp[7641]=36;
dp[7642]=54;
dp[7643]=42;
dp[7644]=12;
dp[7645]=42;
dp[7646]=0;
dp[7647]=60;
dp[7648]=0;
dp[7649]=51;
dp[7650]=48;
dp[7651]=54;
dp[7652]=9;
dp[7653]=36;
dp[7654]=27;
dp[7655]=24;
dp[7656]=6;
dp[7657]=84;
dp[7658]=18;
dp[7659]=48;
dp[7660]=30;
dp[7661]=42;
dp[7662]=0;
dp[7663]=78;
dp[7664]=0;
dp[7665]=48;
dp[7666]=27;
dp[7667]=27;
dp[7668]=48;
dp[7669]=42;
dp[7670]=18;
dp[7671]=36;
dp[7672]=0;
dp[7673]=39;
dp[7674]=18;
dp[7675]=99;
dp[7676]=24;
dp[7677]=102;
dp[7678]=0;
dp[7679]=18;
dp[7680]=0;
dp[7681]=48;
dp[7682]=18;
dp[7683]=72;
dp[7684]=15;
dp[7685]=36;
dp[7686]=12;
dp[7687]=84;
dp[7688]=12;
dp[7689]=24;
dp[7690]=12;
dp[7691]=30;
dp[7692]=39;
dp[7693]=84;
dp[7694]=0;
dp[7695]=36;
dp[7696]=12;
dp[7697]=39;
dp[7698]=39;
dp[7699]=63;
dp[7700]=24;
dp[7701]=42;
dp[7702]=24;
dp[7703]=66;
dp[7704]=6;
dp[7705]=72;
dp[7706]=18;
dp[7707]=18;
dp[7708]=24;
dp[7709]=30;
dp[7710]=0;
dp[7711]=60;
dp[7712]=6;
dp[7713]=48;
dp[7714]=42;
dp[7715]=36;
dp[7716]=15;
dp[7717]=78;
dp[7718]=6;
dp[7719]=48;
dp[7720]=30;
dp[7721]=12;
dp[7722]=36;
dp[7723]=54;
dp[7724]=12;
dp[7725]=36;
dp[7726]=0;
dp[7727]=42;
dp[7728]=6;
dp[7729]=45;
dp[7730]=6;
dp[7731]=69;
dp[7732]=24;
dp[7733]=72;
dp[7734]=21;
dp[7735]=48;
dp[7736]=0;
dp[7737]=57;
dp[7738]=48;
dp[7739]=12;
dp[7740]=24;
dp[7741]=48;
dp[7742]=0;
dp[7743]=48;
dp[7744]=3;
dp[7745]=48;
dp[7746]=15;
dp[7747]=78;
dp[7748]=24;
dp[7749]=60;
dp[7750]=18;
dp[7751]=12;
dp[7752]=12;
dp[7753]=111;
dp[7754]=24;
dp[7755]=54;
dp[7756]=24;
dp[7757]=24;
dp[7758]=0;
dp[7759]=48;
dp[7760]=6;
dp[7761]=36;
dp[7762]=33;
dp[7763]=42;
dp[7764]=6;
dp[7765]=54;
dp[7766]=9;
dp[7767]=72;
dp[7768]=18;
dp[7769]=27;
dp[7770]=30;
dp[7771]=30;
dp[7772]=12;
dp[7773]=54;
dp[7774]=0;
dp[7775]=66;
dp[7776]=4;
dp[7777]=78;
dp[7778]=21;
dp[7779]=24;
dp[7780]=54;
dp[7781]=18;
dp[7782]=24;
dp[7783]=54;
dp[7784]=6;
dp[7785]=60;
dp[7786]=24;
dp[7787]=54;
dp[7788]=21;
dp[7789]=78;
dp[7790]=0;
dp[7791]=36;
dp[7792]=18;
dp[7793]=54;
dp[7794]=30;
dp[7795]=66;
dp[7796]=18;
dp[7797]=48;
dp[7798]=30;
dp[7799]=24;
dp[7800]=0;
dp[7801]=42;
dp[7802]=12;
dp[7803]=99;
dp[7804]=36;
dp[7805]=30;
dp[7806]=0;
dp[7807]=90;
dp[7808]=6;
dp[7809]=18;
dp[7810]=30;
dp[7811]=30;
dp[7812]=24;
dp[7813]=78;
dp[7814]=6;
dp[7815]=66;
dp[7816]=9;
dp[7817]=24;
dp[7818]=42;
dp[7819]=78;
dp[7820]=30;
dp[7821]=42;
dp[7822]=0;
dp[7823]=18;
dp[7824]=12;
dp[7825]=102;
dp[7826]=6;
dp[7827]=33;
dp[7828]=24;
dp[7829]=18;
dp[7830]=12;
dp[7831]=66;
dp[7832]=9;
dp[7833]=54;
dp[7834]=24;
dp[7835]=24;
dp[7836]=36;
dp[7837]=84;
dp[7838]=0;
dp[7839]=60;
dp[7840]=6;
dp[7841]=39;
dp[7842]=15;
dp[7843]=78;
dp[7844]=12;
dp[7845]=42;
dp[7846]=21;
dp[7847]=42;
dp[7848]=18;
dp[7849]=42;
dp[7850]=18;
dp[7851]=18;
dp[7852]=42;
dp[7853]=24;
dp[7854]=0;
dp[7855]=48;
dp[7856]=3;
dp[7857]=105;
dp[7858]=51;
dp[7859]=42;
dp[7860]=30;
dp[7861]=42;
dp[7862]=18;
dp[7863]=72;
dp[7864]=0;
dp[7865]=24;
dp[7866]=24;
dp[7867]=102;
dp[7868]=6;
dp[7869]=36;
dp[7870]=0;
dp[7871]=36;
dp[7872]=9;
dp[7873]=99;
dp[7874]=12;
dp[7875]=48;
dp[7876]=21;
dp[7877]=48;
dp[7878]=18;
dp[7879]=42;
dp[7880]=6;
dp[7881]=36;
dp[7882]=42;
dp[7883]=18;
dp[7884]=12;
dp[7885]=78;
dp[7886]=0;
dp[7887]=48;
dp[7888]=30;
dp[7889]=30;
dp[7890]=18;
dp[7891]=36;
dp[7892]=30;
dp[7893]=42;
dp[7894]=9;
dp[7895]=42;
dp[7896]=6;
dp[7897]=60;
dp[7898]=12;
dp[7899]=39;
dp[7900]=30;
dp[7901]=24;
dp[7902]=0;
dp[7903]=78;
dp[7904]=0;
dp[7905]=48;
dp[7906]=30;
dp[7907]=39;
dp[7908]=27;
dp[7909]=102;
dp[7910]=24;
dp[7911]=30;
dp[7912]=12;
dp[7913]=51;
dp[7914]=12;
dp[7915]=66;
dp[7916]=9;
dp[7917]=48;
dp[7918]=0;
dp[7919]=30;
dp[7920]=18;
dp[7921]=45;
dp[7922]=39;
dp[7923]=87;
dp[7924]=30;
dp[7925]=36;
dp[7926]=9;
dp[7927]=72;
dp[7928]=0;
dp[7929]=60;
dp[7930]=24;
dp[7931]=30;
dp[7932]=36;
dp[7933]=54;
dp[7934]=0;
dp[7935]=48;
dp[7936]=0;
dp[7937]=45;
dp[7938]=36;
dp[7939]=45;
dp[7940]=18;
dp[7941]=42;
dp[7942]=27;
dp[7943]=60;
dp[7944]=9;
dp[7945]=66;
dp[7946]=12;
dp[7947]=78;
dp[7948]=42;
dp[7949]=18;
dp[7950]=0;
dp[7951]=60;
dp[7952]=6;
dp[7953]=60;
dp[7954]=33;
dp[7955]=36;
dp[7956]=24;
dp[7957]=96;
dp[7958]=12;
dp[7959]=18;
dp[7960]=12;
dp[7961]=12;
dp[7962]=36;
dp[7963]=72;
dp[7964]=0;
dp[7965]=78;
dp[7966]=0;
dp[7967]=36;
dp[7968]=6;
dp[7969]=60;
dp[7970]=24;
dp[7971]=27;
dp[7972]=51;
dp[7973]=42;
dp[7974]=24;
dp[7975]=84;
dp[7976]=12;
dp[7977]=57;
dp[7978]=48;
dp[7979]=30;
dp[7980]=24;
dp[7981]=42;
dp[7982]=0;
dp[7983]=60;
dp[7984]=12;
dp[7985]=24;
dp[7986]=18;
dp[7987]=96;
dp[7988]=12;
dp[7989]=30;
dp[7990]=30;
dp[7991]=30;
dp[7992]=0;
dp[7993]=93;
dp[7994]=18;
dp[7995]=48;
dp[7996]=18;
dp[7997]=60;
dp[7998]=0;
dp[7999]=48;
dp[8000]=6;
dp[8001]=54;
dp[8002]=36;
dp[8003]=30;
dp[8004]=12;
dp[8005]=42;
dp[8006]=9;
dp[8007]=60;
dp[8008]=18;
dp[8009]=12;
dp[8010]=24;
dp[8011]=69;
dp[8012]=6;
dp[8013]=60;
dp[8014]=0;
dp[8015]=54;
dp[8016]=6;
dp[8017]=33;
dp[8018]=15;
dp[8019]=60;
dp[8020]=36;
dp[8021]=30;
dp[8022]=18;
dp[8023]=90;
dp[8024]=3;
dp[8025]=72;
dp[8026]=24;
dp[8027]=54;
dp[8028]=54;
dp[8029]=42;
dp[8030]=0;
dp[8031]=18;
dp[8032]=9;
dp[8033]=60;
dp[8034]=30;
dp[8035]=84;
dp[8036]=18;
dp[8037]=48;
dp[8038]=24;
dp[8039]=12;
dp[8040]=6;
dp[8041]=66;
dp[8042]=36;
dp[8043]=24;
dp[8044]=27;
dp[8045]=24;
dp[8046]=0;
dp[8047]=42;
dp[8048]=12;
dp[8049]=39;
dp[8050]=42;
dp[8051]=27;
dp[8052]=18;
dp[8053]=108;
dp[8054]=9;
dp[8055]=78;
dp[8056]=0;
dp[8057]=48;
dp[8058]=12;
dp[8059]=54;
dp[8060]=30;
dp[8061]=30;
dp[8062]=0;
dp[8063]=36;
dp[8064]=0;
dp[8065]=48;
dp[8066]=12;
dp[8067]=75;
dp[8068]=39;
dp[8069]=30;
dp[8070]=6;
dp[8071]=42;
dp[8072]=9;
dp[8073]=66;
dp[8074]=30;
dp[8075]=33;
dp[8076]=18;
dp[8077]=96;
dp[8078]=0;
dp[8079]=48;
dp[8080]=18;
dp[8081]=39;
dp[8082]=36;
dp[8083]=102;
dp[8084]=12;
dp[8085]=54;
dp[8086]=18;
dp[8087]=24;
dp[8088]=9;
dp[8089]=45;
dp[8090]=24;
dp[8091]=72;
dp[8092]=30;
dp[8093]=36;
dp[8094]=0;
dp[8095]=78;
dp[8096]=6;
dp[8097]=63;
dp[8098]=36;
dp[8099]=36;
dp[8100]=21;
dp[8101]=60;
dp[8102]=9;
dp[8103]=36;
dp[8104]=12;
dp[8105]=54;
dp[8106]=24;
dp[8107]=78;
dp[8108]=27;
dp[8109]=42;
dp[8110]=0;
dp[8111]=42;
dp[8112]=18;
dp[8113]=60;
dp[8114]=9;
dp[8115]=24;
dp[8116]=24;
dp[8117]=54;
dp[8118]=39;
dp[8119]=84;
dp[8120]=0;
dp[8121]=27;
dp[8122]=36;
dp[8123]=39;
dp[8124]=12;
dp[8125]=84;
dp[8126]=0;
dp[8127]=66;
dp[8128]=0;
dp[8129]=21;
dp[8130]=30;
dp[8131]=30;
dp[8132]=42;
dp[8133]=66;
dp[8134]=18;
dp[8135]=18;
dp[8136]=18;
dp[8137]=78;
dp[8138]=12;
dp[8139]=48;
dp[8140]=42;
dp[8141]=36;
dp[8142]=0;
dp[8143]=90;
dp[8144]=6;
dp[8145]=48;
dp[8146]=33;
dp[8147]=39;
dp[8148]=24;
dp[8149]=48;
dp[8150]=15;
dp[8151]=54;
dp[8152]=15;
dp[8153]=54;
dp[8154]=24;
dp[8155]=48;
dp[8156]=18;
dp[8157]=60;
dp[8158]=0;
dp[8159]=24;
dp[8160]=0;
dp[8161]=48;
dp[8162]=24;
dp[8163]=78;
dp[8164]=24;
dp[8165]=36;
dp[8166]=9;
dp[8167]=90;
dp[8168]=12;
dp[8169]=42;
dp[8170]=24;
dp[8171]=30;
dp[8172]=45;
dp[8173]=54;
dp[8174]=0;
dp[8175]=66;
dp[8176]=12;
dp[8177]=24;
dp[8178]=12;
dp[8179]=60;
dp[8180]=6;
dp[8181]=48;
dp[8182]=33;
dp[8183]=48;
dp[8184]=0;
dp[8185]=60;
dp[8186]=6;
dp[8187]=51;
dp[8188]=54;
dp[8189]=12;
dp[8190]=0;
dp[8191]=30;
dp[8192]=0;
dp[8193]=69;
dp[8194]=21;
dp[8195]=42;
dp[8196]=15;
dp[8197]=72;
dp[8198]=15;
dp[8199]=48;
dp[8200]=21;
dp[8201]=33;
dp[8202]=36;
dp[8203]=96;
dp[8204]=6;
dp[8205]=30;
dp[8206]=0;
dp[8207]=54;
dp[8208]=6;
dp[8209]=87;
dp[8210]=30;
dp[8211]=42;
dp[8212]=30;
dp[8213]=36;
dp[8214]=13;
dp[8215]=42;
dp[8216]=6;
dp[8217]=84;
dp[8218]=48;
dp[8219]=18;
dp[8220]=18;
dp[8221]=72;
dp[8222]=0;
dp[8223]=54;
dp[8224]=12;
dp[8225]=30;
dp[8226]=30;
dp[8227]=75;
dp[8228]=24;
dp[8229]=36;
dp[8230]=24;
dp[8231]=42;
dp[8232]=18;
dp[8233]=78;
dp[8234]=12;
dp[8235]=36;
dp[8236]=30;
dp[8237]=72;
dp[8238]=0;
dp[8239]=48;
dp[8240]=6;
dp[8241]=33;
dp[8242]=36;
dp[8243]=57;
dp[8244]=36;
dp[8245]=66;
dp[8246]=6;
dp[8247]=54;
dp[8248]=0;
dp[8249]=27;
dp[8250]=36;
dp[8251]=66;
dp[8252]=12;
dp[8253]=90;
dp[8254]=0;
dp[8255]=24;
dp[8256]=3;
dp[8257]=96;
dp[8258]=24;
dp[8259]=27;
dp[8260]=24;
dp[8261]=18;
dp[8262]=24;
dp[8263]=108;
dp[8264]=12;
dp[8265]=42;
dp[8266]=48;
dp[8267]=24;
dp[8268]=18;
dp[8269]=30;
dp[8270]=0;
dp[8271]=54;
dp[8272]=18;
dp[8273]=48;
dp[8274]=12;
dp[8275]=75;
dp[8276]=18;
dp[8277]=90;
dp[8278]=21;
dp[8279]=36;
dp[8280]=12;
dp[8281]=72;
dp[8282]=12;
dp[8283]=45;
dp[8284]=24;
dp[8285]=24;
dp[8286]=0;
dp[8287]=114;
dp[8288]=0;
dp[8289]=27;
dp[8290]=30;
dp[8291]=39;
dp[8292]=33;
dp[8293]=48;
dp[8294]=12;
dp[8295]=54;
dp[8296]=12;
dp[8297]=18;
dp[8298]=42;
dp[8299]=45;
dp[8300]=27;
dp[8301]=48;
dp[8302]=0;
dp[8303]=48;
dp[8304]=6;
dp[8305]=90;
dp[8306]=9;
dp[8307]=60;
dp[8308]=42;
dp[8309]=36;
dp[8310]=12;
dp[8311]=48;
dp[8312]=0;
dp[8313]=36;
dp[8314]=42;
dp[8315]=42;
dp[8316]=18;
dp[8317]=78;
dp[8318]=0;
dp[8319]=30;
dp[8320]=6;
dp[8321]=24;
dp[8322]=33;
dp[8323]=78;
dp[8324]=9;
dp[8325]=84;
dp[8326]=30;
dp[8327]=18;
dp[8328]=15;
dp[8329]=63;
dp[8330]=18;
dp[8331]=51;
dp[8332]=30;
dp[8333]=48;
dp[8334]=0;
dp[8335]=72;
dp[8336]=6;
dp[8337]=36;
dp[8338]=51;
dp[8339]=24;
dp[8340]=30;
dp[8341]=48;
dp[8342]=21;
dp[8343]=96;
dp[8344]=6;
dp[8345]=24;
dp[8346]=6;
dp[8347]=93;
dp[8348]=12;
dp[8349]=48;
dp[8350]=0;
dp[8351]=18;
dp[8352]=6;
dp[8353]=69;
dp[8354]=18;
dp[8355]=36;
dp[8356]=18;
dp[8357]=24;
dp[8358]=18;
dp[8359]=24;
dp[8360]=6;
dp[8361]=54;
dp[8362]=36;
dp[8363]=51;
dp[8364]=33;
dp[8365]=96;
dp[8366]=0;
dp[8367]=36;
dp[8368]=15;
dp[8369]=27;
dp[8370]=30;
dp[8371]=54;
dp[8372]=30;
dp[8373]=42;
dp[8374]=12;
dp[8375]=36;
dp[8376]=0;
dp[8377]=117;
dp[8378]=36;
dp[8379]=54;
dp[8380]=36;
dp[8381]=24;
dp[8382]=0;
dp[8383]=96;
dp[8384]=3;
dp[8385]=72;
dp[8386]=36;
dp[8387]=57;
dp[8388]=27;
dp[8389]=54;
dp[8390]=6;
dp[8391]=54;
dp[8392]=21;
dp[8393]=36;
dp[8394]=12;
dp[8395]=66;
dp[8396]=33;
dp[8397]=60;
dp[8398]=0;
dp[8399]=30;
dp[8400]=24;
dp[8401]=24;
dp[8402]=15;
dp[8403]=63;
dp[8404]=30;
dp[8405]=42;
dp[8406]=24;
dp[8407]=78;
dp[8408]=9;
dp[8409]=39;
dp[8410]=30;
dp[8411]=24;
dp[8412]=24;
dp[8413]=138;
dp[8414]=0;
dp[8415]=42;
dp[8416]=0;
dp[8417]=54;
dp[8418]=24;
dp[8419]=57;
dp[8420]=12;
dp[8421]=30;
dp[8422]=24;
dp[8423]=42;
dp[8424]=18;
dp[8425]=54;
dp[8426]=6;
dp[8427]=60;
dp[8428]=33;
dp[8429]=24;
dp[8430]=0;
dp[8431]=72;
dp[8432]=6;
dp[8433]=84;
dp[8434]=24;
dp[8435]=42;
dp[8436]=6;
dp[8437]=66;
dp[8438]=15;
dp[8439]=36;
dp[8440]=0;
dp[8441]=42;
dp[8442]=48;
dp[8443]=51;
dp[8444]=18;
dp[8445]=66;
dp[8446]=0;
dp[8447]=60;
dp[8448]=3;
dp[8449]=60;
dp[8450]=12;
dp[8451]=60;
dp[8452]=57;
dp[8453]=42;
dp[8454]=9;
dp[8455]=72;
dp[8456]=12;
dp[8457]=60;
dp[8458]=42;
dp[8459]=27;
dp[8460]=24;
dp[8461]=60;
dp[8462]=0;
dp[8463]=42;
dp[8464]=18;
dp[8465]=24;
dp[8466]=30;
dp[8467]=48;
dp[8468]=30;
dp[8469]=36;
dp[8470]=18;
dp[8471]=30;
dp[8472]=9;
dp[8473]=78;
dp[8474]=12;
dp[8475]=51;
dp[8476]=18;
dp[8477]=30;
dp[8478]=0;
dp[8479]=60;
dp[8480]=0;
dp[8481]=12;
dp[8482]=57;
dp[8483]=51;
dp[8484]=18;
dp[8485]=78;
dp[8486]=6;
dp[8487]=102;
dp[8488]=12;
dp[8489]=30;
dp[8490]=24;
dp[8491]=48;
dp[8492]=27;
dp[8493]=36;
dp[8494]=0;
dp[8495]=30;
dp[8496]=12;
dp[8497]=126;
dp[8498]=6;
dp[8499]=27;
dp[8500]=36;
dp[8501]=30;
dp[8502]=18;
dp[8503]=66;
dp[8504]=0;
dp[8505]=60;
dp[8506]=30;
dp[8507]=48;
dp[8508]=36;
dp[8509]=48;
dp[8510]=0;
dp[8511]=24;
dp[8512]=6;
dp[8513]=39;
dp[8514]=24;
dp[8515]=96;
dp[8516]=12;
dp[8517]=90;
dp[8518]=33;
dp[8519]=36;
dp[8520]=6;
dp[8521]=39;
dp[8522]=6;
dp[8523]=90;
dp[8524]=27;
dp[8525]=36;
dp[8526]=0;
dp[8527]=60;
dp[8528]=12;
dp[8529]=45;
dp[8530]=42;
dp[8531]=30;
dp[8532]=30;
dp[8533]=72;
dp[8534]=12;
dp[8535]=36;
dp[8536]=9;
dp[8537]=39;
dp[8538]=36;
dp[8539]=69;
dp[8540]=24;
dp[8541]=48;
dp[8542]=0;
dp[8543]=36;
dp[8544]=6;
dp[8545]=66;
dp[8546]=15;
dp[8547]=72;
dp[8548]=39;
dp[8549]=36;
dp[8550]=27;
dp[8551]=54;
dp[8552]=18;
dp[8553]=57;
dp[8554]=30;
dp[8555]=42;
dp[8556]=12;
dp[8557]=60;
dp[8558]=0;
dp[8559]=84;
dp[8560]=24;
dp[8561]=36;
dp[8562]=27;
dp[8563]=72;
dp[8564]=12;
dp[8565]=48;
dp[8566]=21;
dp[8567]=60;
dp[8568]=0;
dp[8569]=51;
dp[8570]=30;
dp[8571]=27;
dp[8572]=30;
dp[8573]=90;
dp[8574]=0;
dp[8575]=78;
dp[8576]=0;
dp[8577]=42;
dp[8578]=57;
dp[8579]=12;
dp[8580]=30;
dp[8581]=48;
dp[8582]=18;
dp[8583]=42;
dp[8584]=6;
dp[8585]=48;
dp[8586]=24;
dp[8587]=90;
dp[8588]=15;
dp[8589]=42;
dp[8590]=0;
dp[8591]=12;
dp[8592]=15;
dp[8593]=84;
dp[8594]=24;
dp[8595]=72;
dp[8596]=18;
dp[8597]=48;
dp[8598]=21;
dp[8599]=66;
dp[8600]=3;
dp[8601]=54;
dp[8602]=42;
dp[8603]=30;
dp[8604]=24;
dp[8605]=48;
dp[8606]=0;
dp[8607]=36;
dp[8608]=18;
dp[8609]=27;
dp[8610]=12;
dp[8611]=42;
dp[8612]=9;
dp[8613]=108;
dp[8614]=18;
dp[8615]=36;
dp[8616]=12;
dp[8617]=96;
dp[8618]=24;
dp[8619]=21;
dp[8620]=30;
dp[8621]=24;
dp[8622]=0;
dp[8623]=96;
dp[8624]=9;
dp[8625]=54;
dp[8626]=18;
dp[8627]=75;
dp[8628]=30;
dp[8629]=54;
dp[8630]=18;
dp[8631]=36;
dp[8632]=0;
dp[8633]=39;
dp[8634]=18;
dp[8635]=84;
dp[8636]=18;
dp[8637]=42;
dp[8638]=0;
dp[8639]=24;
dp[8640]=6;
dp[8641]=54;
dp[8642]=18;
dp[8643]=57;
dp[8644]=42;
dp[8645]=24;
dp[8646]=9;
dp[8647]=84;
dp[8648]=18;
dp[8649]=48;
dp[8650]=42;
dp[8651]=27;
dp[8652]=30;
dp[8653]=78;
dp[8654]=0;
dp[8655]=60;
dp[8656]=0;
dp[8657]=30;
dp[8658]=48;
dp[8659]=36;
dp[8660]=6;
dp[8661]=30;
dp[8662]=36;
dp[8663]=6;
dp[8664]=10;
dp[8665]=78;
dp[8666]=12;
dp[8667]=51;
dp[8668]=48;
dp[8669]=48;
dp[8670]=0;
dp[8671]=90;
dp[8672]=0;
dp[8673]=75;
dp[8674]=9;
dp[8675]=42;
dp[8676]=24;
dp[8677]=48;
dp[8678]=15;
dp[8679]=72;
dp[8680]=12;
dp[8681]=33;
dp[8682]=42;
dp[8683]=108;
dp[8684]=12;
dp[8685]=54;
dp[8686]=0;
dp[8687]=54;
dp[8688]=18;
dp[8689]=51;
dp[8690]=42;
dp[8691]=36;
dp[8692]=48;
dp[8693]=48;
dp[8694]=12;
dp[8695]=72;
dp[8696]=0;
dp[8697]=42;
dp[8698]=18;
dp[8699]=45;
dp[8700]=30;
dp[8701]=66;
dp[8702]=0;
dp[8703]=78;
dp[8704]=3;
dp[8705]=36;
dp[8706]=15;
dp[8707]=78;
dp[8708]=30;
dp[8709]=30;
dp[8710]=30;
dp[8711]=30;
dp[8712]=15;
dp[8713]=102;
dp[8714]=12;
dp[8715]=54;
dp[8716]=18;
dp[8717]=30;
dp[8718]=0;
dp[8719]=36;
dp[8720]=6;
dp[8721]=81;
dp[8722]=48;
dp[8723]=12;
dp[8724]=24;
dp[8725]=108;
dp[8726]=6;
dp[8727]=78;
dp[8728]=18;
dp[8729]=24;
dp[8730]=36;
dp[8731]=33;
dp[8732]=18;
dp[8733]=30;
dp[8734]=0;
dp[8735]=30;
dp[8736]=0;
dp[8737]=108;
dp[8738]=21;
dp[8739]=54;
dp[8740]=42;
dp[8741]=18;
dp[8742]=18;
dp[8743]=90;
dp[8744]=6;
dp[8745]=30;
dp[8746]=48;
dp[8747]=69;
dp[8748]=36;
dp[8749]=48;
dp[8750]=0;
dp[8751]=24;
dp[8752]=15;
dp[8753]=24;
dp[8754]=15;
dp[8755]=84;
dp[8756]=24;
dp[8757]=114;
dp[8758]=6;
dp[8759]=30;
dp[8760]=0;
dp[8761]=48;
dp[8762]=6;
dp[8763]=60;
dp[8764]=42;
dp[8765]=24;
dp[8766]=0;
dp[8767]=102;
dp[8768]=12;
dp[8769]=42;
dp[8770]=42;
dp[8771]=27;
dp[8772]=21;
dp[8773]=78;
dp[8774]=9;
dp[8775]=42;
dp[8776]=24;
dp[8777]=51;
dp[8778]=24;
dp[8779]=42;
dp[8780]=12;
dp[8781]=48;
dp[8782]=0;
dp[8783]=60;
dp[8784]=12;
dp[8785]=66;
dp[8786]=6;
dp[8787]=42;
dp[8788]=24;
dp[8789]=30;
dp[8790]=24;
dp[8791]=42;
dp[8792]=0;
dp[8793]=78;
dp[8794]=24;
dp[8795]=54;
dp[8796]=12;
dp[8797]=66;
dp[8798]=0;
dp[8799]=30;
dp[8800]=6;
dp[8801]=24;
dp[8802]=51;
dp[8803]=99;
dp[8804]=18;
dp[8805]=60;
dp[8806]=24;
dp[8807]=42;
dp[8808]=18;
dp[8809]=54;
dp[8810]=6;
dp[8811]=45;
dp[8812]=60;
dp[8813]=36;
dp[8814]=0;
dp[8815]=54;
dp[8816]=6;
dp[8817]=39;
dp[8818]=39;
dp[8819]=39;
dp[8820]=30;
dp[8821]=66;
dp[8822]=18;
dp[8823]=72;
dp[8824]=0;
dp[8825]=51;
dp[8826]=24;
dp[8827]=102;
dp[8828]=12;
dp[8829]=54;
dp[8830]=0;
dp[8831]=24;
dp[8832]=0;
dp[8833]=102;
dp[8834]=12;
dp[8835]=48;
dp[8836]=24;
dp[8837]=42;
dp[8838]=36;
dp[8839]=60;
dp[8840]=0;
dp[8841]=12;
dp[8842]=48;
dp[8843]=18;
dp[8844]=12;
dp[8845]=54;
dp[8846]=0;
dp[8847]=84;
dp[8848]=18;
dp[8849]=39;
dp[8850]=9;
dp[8851]=84;
dp[8852]=30;
dp[8853]=66;
dp[8854]=18;
dp[8855]=48;
dp[8856]=15;
dp[8857]=72;
dp[8858]=48;
dp[8859]=39;
dp[8860]=42;
dp[8861]=48;
dp[8862]=0;
dp[8863]=60;
dp[8864]=0;
dp[8865]=84;
dp[8866]=30;
dp[8867]=45;
dp[8868]=33;
dp[8869]=54;
dp[8870]=6;
dp[8871]=54;
dp[8872]=30;
dp[8873]=33;
dp[8874]=30;
dp[8875]=90;
dp[8876]=6;
dp[8877]=54;
dp[8878]=0;
dp[8879]=24;
dp[8880]=6;
dp[8881]=72;
dp[8882]=27;
dp[8883]=78;
dp[8884]=12;
dp[8885]=24;
dp[8886]=15;
dp[8887]=66;
dp[8888]=0;
dp[8889]=54;
dp[8890]=36;
dp[8891]=21;
dp[8892]=42;
dp[8893]=114;
dp[8894]=0;
dp[8895]=60;
dp[8896]=3;
dp[8897]=30;
dp[8898]=33;
dp[8899]=54;
dp[8900]=27;
dp[8901]=30;
dp[8902]=33;
dp[8903]=60;
dp[8904]=6;
dp[8905]=54;
dp[8906]=12;
dp[8907]=48;
dp[8908]=33;
dp[8909]=36;
dp[8910]=0;
dp[8911]=42;
dp[8912]=12;
dp[8913]=45;
dp[8914]=39;
dp[8915]=24;
dp[8916]=36;
dp[8917]=96;
dp[8918]=18;
dp[8919]=24;
dp[8920]=12;
dp[8921]=33;
dp[8922]=18;
dp[8923]=99;
dp[8924]=18;
dp[8925]=66;
dp[8926]=0;
dp[8927]=36;
dp[8928]=0;
dp[8929]=51;
dp[8930]=24;
dp[8931]=30;
dp[8932]=30;
dp[8933]=36;
dp[8934]=15;
dp[8935]=84;
dp[8936]=6;
dp[8937]=102;
dp[8938]=48;
dp[8939]=48;
dp[8940]=18;
dp[8941]=60;
dp[8942]=0;
dp[8943]=72;
dp[8944]=12;
dp[8945]=36;
dp[8946]=42;
dp[8947]=60;
dp[8948]=12;
dp[8949]=24;
dp[8950]=21;
dp[8951]=30;
dp[8952]=0;
dp[8953]=54;
dp[8954]=18;
dp[8955]=60;
dp[8956]=18;
dp[8957]=42;
dp[8958]=0;
dp[8959]=66;
dp[8960]=6;
dp[8961]=24;
dp[8962]=24;
dp[8963]=54;
dp[8964]=15;
dp[8965]=78;
dp[8966]=12;
dp[8967]=42;
dp[8968]=27;
dp[8969]=27;
dp[8970]=30;
dp[8971]=51;
dp[8972]=27;
dp[8973]=78;
dp[8974]=0;
dp[8975]=48;
dp[8976]=6;
dp[8977]=120;
dp[8978]=27;
dp[8979]=48;
dp[8980]=42;
dp[8981]=24;
dp[8982]=12;
dp[8983]=54;
dp[8984]=6;
dp[8985]=54;
dp[8986]=24;
dp[8987]=48;
dp[8988]=36;
dp[8989]=66;
dp[8990]=0;
dp[8991]=78;
dp[8992]=9;
dp[8993]=57;
dp[8994]=21;
dp[8995]=48;
dp[8996]=18;
dp[8997]=54;
dp[8998]=33;
dp[8999]=24;
dp[9000]=30;
dp[9001]=84;
dp[9002]=18;
dp[9003]=45;
dp[9004]=33;
dp[9005]=30;
dp[9006]=0;
dp[9007]=126;
dp[9008]=9;
dp[9009]=36;
dp[9010]=30;
dp[9011]=27;
dp[9012]=30;
dp[9013]=66;
dp[9014]=18;
dp[9015]=54;
dp[9016]=0;
dp[9017]=36;
dp[9018]=42;
dp[9019]=48;
dp[9020]=6;
dp[9021]=42;
dp[9022]=0;
dp[9023]=54;
dp[9024]=6;
dp[9025]=57;
dp[9026]=12;
dp[9027]=84;
dp[9028]=54;
dp[9029]=48;
dp[9030]=6;
dp[9031]=60;
dp[9032]=6;
dp[9033]=63;
dp[9034]=18;
dp[9035]=42;
dp[9036]=36;
dp[9037]=78;
dp[9038]=0;
dp[9039]=24;
dp[9040]=24;
dp[9041]=33;
dp[9042]=24;
dp[9043]=105;
dp[9044]=24;
dp[9045]=66;
dp[9046]=27;
dp[9047]=48;
dp[9048]=0;
dp[9049]=48;
dp[9050]=30;
dp[9051]=60;
dp[9052]=30;
dp[9053]=54;
dp[9054]=0;
dp[9055]=42;
dp[9056]=3;
dp[9057]=75;
dp[9058]=48;
dp[9059]=24;
dp[9060]=12;
dp[9061]=66;
dp[9062]=12;
dp[9063]=96;
dp[9064]=6;
dp[9065]=30;
dp[9066]=12;
dp[9067]=87;
dp[9068]=21;
dp[9069]=36;
dp[9070]=0;
dp[9071]=30;
dp[9072]=24;
dp[9073]=69;
dp[9074]=12;
dp[9075]=57;
dp[9076]=30;
dp[9077]=48;
dp[9078]=24;
dp[9079]=54;
dp[9080]=0;
dp[9081]=42;
dp[9082]=54;
dp[9083]=24;
dp[9084]=24;
dp[9085]=72;
dp[9086]=0;
dp[9087]=60;
dp[9088]=0;
dp[9089]=48;
dp[9090]=24;
dp[9091]=69;
dp[9092]=24;
dp[9093]=42;
dp[9094]=18;
dp[9095]=36;
dp[9096]=12;
dp[9097]=66;
dp[9098]=24;
dp[9099]=36;
dp[9100]=42;
dp[9101]=18;
dp[9102]=0;
dp[9103]=78;
dp[9104]=9;
dp[9105]=48;
dp[9106]=36;
dp[9107]=42;
dp[9108]=42;
dp[9109]=36;
dp[9110]=12;
dp[9111]=36;
dp[9112]=21;
dp[9113]=78;
dp[9114]=18;
dp[9115]=48;
dp[9116]=12;
dp[9117]=102;
dp[9118]=0;
dp[9119]=18;
dp[9120]=12;
dp[9121]=54;
dp[9122]=24;
dp[9123]=45;
dp[9124]=27;
dp[9125]=42;
dp[9126]=13;
dp[9127]=108;
dp[9128]=12;
dp[9129]=39;
dp[9130]=24;
dp[9131]=42;
dp[9132]=27;
dp[9133]=102;
dp[9134]=0;
dp[9135]=60;
dp[9136]=6;
dp[9137]=39;
dp[9138]=24;
dp[9139]=54;
dp[9140]=12;
dp[9141]=54;
dp[9142]=24;
dp[9143]=24;
dp[9144]=0;
dp[9145]=114;
dp[9146]=24;
dp[9147]=63;
dp[9148]=48;
dp[9149]=30;
dp[9150]=0;
dp[9151]=48;
dp[9152]=6;
dp[9153]=69;
dp[9154]=36;
dp[9155]=18;
dp[9156]=12;
dp[9157]=72;
dp[9158]=6;
dp[9159]=48;
dp[9160]=18;
dp[9161]=33;
dp[9162]=54;
dp[9163]=117;
dp[9164]=12;
dp[9165]=42;
dp[9166]=0;
dp[9167]=66;
dp[9168]=12;
dp[9169]=48;
dp[9170]=6;
dp[9171]=54;
dp[9172]=36;
dp[9173]=42;
dp[9174]=21;
dp[9175]=102;
dp[9176]=6;
dp[9177]=48;
dp[9178]=54;
dp[9179]=33;
dp[9180]=30;
dp[9181]=48;
dp[9182]=0;
dp[9183]=72;
dp[9184]=0;
dp[9185]=30;
dp[9186]=24;
dp[9187]=75;
dp[9188]=24;
dp[9189]=84;
dp[9190]=30;
dp[9191]=30;
dp[9192]=0;
dp[9193]=72;
dp[9194]=18;
dp[9195]=30;
dp[9196]=42;
dp[9197]=54;
dp[9198]=0;
dp[9199]=60;
dp[9200]=12;
dp[9201]=36;
dp[9202]=45;
dp[9203]=42;
dp[9204]=12;
dp[9205]=96;
dp[9206]=6;
dp[9207]=66;
dp[9208]=0;
dp[9209]=12;
dp[9210]=36;
dp[9211]=78;
dp[9212]=36;
dp[9213]=42;
dp[9214]=0;
dp[9215]=36;
dp[9216]=0;
dp[9217]=78;
dp[9218]=24;
dp[9219]=48;
dp[9220]=24;
dp[9221]=18;
dp[9222]=30;
dp[9223]=90;
dp[9224]=15;
dp[9225]=96;
dp[9226]=18;
dp[9227]=27;
dp[9228]=21;
dp[9229]=54;
dp[9230]=0;
dp[9231]=24;
dp[9232]=21;
dp[9233]=48;
dp[9234]=27;
dp[9235]=84;
dp[9236]=18;
dp[9237]=48;
dp[9238]=42;
dp[9239]=36;
dp[9240]=6;
dp[9241]=66;
dp[9242]=12;
dp[9243]=108;
dp[9244]=12;
dp[9245]=42;
dp[9246]=0;
dp[9247]=48;
dp[9248]=9;
dp[9249]=27;
dp[9250]=60;
dp[9251]=21;
dp[9252]=36;
dp[9253]=84;
dp[9254]=6;
dp[9255]=36;
dp[9256]=18;
dp[9257]=42;
dp[9258]=18;
dp[9259]=54;
dp[9260]=18;
dp[9261]=60;
dp[9262]=0;
dp[9263]=60;
dp[9264]=15;
dp[9265]=72;
dp[9266]=9;
dp[9267]=99;
dp[9268]=42;
dp[9269]=12;
dp[9270]=12;
dp[9271]=60;
dp[9272]=0;
dp[9273]=57;
dp[9274]=42;
dp[9275]=18;
dp[9276]=18;
dp[9277]=78;
dp[9278]=0;
dp[9279]=42;
dp[9280]=6;
dp[9281]=36;
dp[9282]=36;
dp[9283]=63;
dp[9284]=9;
dp[9285]=42;
dp[9286]=15;
dp[9287]=30;
dp[9288]=18;
dp[9289]=78;
dp[9290]=6;
dp[9291]=24;
dp[9292]=48;
dp[9293]=42;
dp[9294]=0;
dp[9295]=102;
dp[9296]=12;
dp[9297]=75;
dp[9298]=45;
dp[9299]=42;
dp[9300]=30;
dp[9301]=84;
dp[9302]=24;
dp[9303]=66;
dp[9304]=9;
dp[9305]=24;
dp[9306]=30;
dp[9307]=90;
dp[9308]=24;
dp[9309]=42;
dp[9310]=0;
dp[9311]=24;
dp[9312]=3;
dp[9313]=84;
dp[9314]=21;
dp[9315]=84;
dp[9316]=33;
dp[9317]=66;
dp[9318]=24;
dp[9319]=36;
dp[9320]=6;
dp[9321]=36;
dp[9322]=48;
dp[9323]=51;
dp[9324]=18;
dp[9325]=72;
dp[9326]=0;
dp[9327]=66;
dp[9328]=18;
dp[9329]=54;
dp[9330]=30;
dp[9331]=24;
dp[9332]=18;
dp[9333]=48;
dp[9334]=18;
dp[9335]=30;
dp[9336]=0;
dp[9337]=102;
dp[9338]=12;
dp[9339]=45;
dp[9340]=36;
dp[9341]=24;
dp[9342]=0;
dp[9343]=102;
dp[9344]=3;
dp[9345]=42;
dp[9346]=15;
dp[9347]=42;
dp[9348]=54;
dp[9349]=54;
dp[9350]=21;
dp[9351]=66;
dp[9352]=24;
dp[9353]=66;
dp[9354]=30;
dp[9355]=102;
dp[9356]=3;
dp[9357]=66;
dp[9358]=0;
dp[9359]=48;
dp[9360]=12;
dp[9361]=24;
dp[9362]=30;
dp[9363]=45;
dp[9364]=36;
dp[9365]=54;
dp[9366]=6;
dp[9367]=78;
dp[9368]=9;
dp[9369]=48;
dp[9370]=24;
dp[9371]=39;
dp[9372]=36;
dp[9373]=96;
dp[9374]=0;
dp[9375]=66;
dp[9376]=6;
dp[9377]=27;
dp[9378]=27;
dp[9379]=60;
dp[9380]=30;
dp[9381]=18;
dp[9382]=30;
dp[9383]=48;
dp[9384]=12;
dp[9385]=90;
dp[9386]=24;
dp[9387]=60;
dp[9388]=36;
dp[9389]=6;
dp[9390]=0;
dp[9391]=42;
dp[9392]=12;
dp[9393]=78;
dp[9394]=36;
dp[9395]=36;
dp[9396]=24;
dp[9397]=114;
dp[9398]=6;
dp[9399]=60;
dp[9400]=0;
dp[9401]=18;
dp[9402]=6;
dp[9403]=69;
dp[9404]=18;
dp[9405]=84;
dp[9406]=0;
dp[9407]=36;
dp[9408]=6;
dp[9409]=48;
dp[9410]=6;
dp[9411]=39;
dp[9412]=24;
dp[9413]=42;
dp[9414]=24;
dp[9415]=54;
dp[9416]=6;
dp[9417]=72;
dp[9418]=48;
dp[9419]=36;
dp[9420]=42;
dp[9421]=60;
dp[9422]=0;
dp[9423]=48;
dp[9424]=0;
dp[9425]=36;
dp[9426]=18;
dp[9427]=138;
dp[9428]=24;
dp[9429]=30;
dp[9430]=30;
dp[9431]=42;
dp[9432]=18;
dp[9433]=75;
dp[9434]=18;
dp[9435]=48;
dp[9436]=18;
dp[9437]=24;
dp[9438]=0;
dp[9439]=78;
dp[9440]=0;
dp[9441]=78;
dp[9442]=57;
dp[9443]=60;
dp[9444]=9;
dp[9445]=48;
dp[9446]=9;
dp[9447]=36;
dp[9448]=30;
dp[9449]=30;
dp[9450]=42;
dp[9451]=42;
dp[9452]=39;
dp[9453]=84;
dp[9454]=0;
dp[9455]=24;
dp[9456]=12;
dp[9457]=87;
dp[9458]=27;
dp[9459]=30;
dp[9460]=42;
dp[9461]=24;
dp[9462]=24;
dp[9463]=90;
dp[9464]=0;
dp[9465]=36;
dp[9466]=24;
dp[9467]=60;
dp[9468]=36;
dp[9469]=84;
dp[9470]=0;
dp[9471]=42;
dp[9472]=0;
dp[9473]=30;
dp[9474]=21;
dp[9475]=87;
dp[9476]=12;
dp[9477]=72;
dp[9478]=24;
dp[9479]=42;
dp[9480]=12;
dp[9481]=60;
dp[9482]=30;
dp[9483]=72;
dp[9484]=21;
dp[9485]=60;
dp[9486]=0;
dp[9487]=96;
dp[9488]=12;
dp[9489]=30;
dp[9490]=42;
dp[9491]=39;
dp[9492]=18;
dp[9493]=66;
dp[9494]=12;
dp[9495]=84;
dp[9496]=12;
dp[9497]=63;
dp[9498]=42;
dp[9499]=42;
dp[9500]=24;
dp[9501]=42;
dp[9502]=0;
dp[9503]=18;
dp[9504]=6;
dp[9505]=78;
dp[9506]=15;
dp[9507]=75;
dp[9508]=45;
dp[9509]=54;
dp[9510]=12;
dp[9511]=54;
dp[9512]=6;
dp[9513]=84;
dp[9514]=30;
dp[9515]=30;
dp[9516]=18;
dp[9517]=54;
dp[9518]=0;
dp[9519]=42;
dp[9520]=24;
dp[9521]=39;
dp[9522]=27;
dp[9523]=96;
dp[9524]=18;
dp[9525]=42;
dp[9526]=21;
dp[9527]=48;
dp[9528]=0;
dp[9529]=54;
dp[9530]=18;
dp[9531]=33;
dp[9532]=36;
dp[9533]=66;
dp[9534]=0;
dp[9535]=84;
dp[9536]=0;
dp[9537]=75;
dp[9538]=48;
dp[9539]=30;
dp[9540]=42;
dp[9541]=54;
dp[9542]=12;
dp[9543]=54;
dp[9544]=15;
dp[9545]=42;
dp[9546]=30;
dp[9547]=96;
dp[9548]=18;
dp[9549]=42;
dp[9550]=0;
dp[9551]=18;
dp[9552]=6;
dp[9553]=123;
dp[9554]=15;
dp[9555]=48;
dp[9556]=24;
dp[9557]=48;
dp[9558]=39;
dp[9559]=42;
dp[9560]=6;
dp[9561]=21;
dp[9562]=54;
dp[9563]=45;
dp[9564]=12;
dp[9565]=60;
dp[9566]=0;
dp[9567]=90;
dp[9568]=12;
dp[9569]=30;
dp[9570]=36;
dp[9571]=45;
dp[9572]=18;
dp[9573]=72;
dp[9574]=21;
dp[9575]=78;
dp[9576]=12;
dp[9577]=30;
dp[9578]=12;
dp[9579]=60;
dp[9580]=30;
dp[9581]=18;
dp[9582]=0;
dp[9583]=78;
dp[9584]=6;
dp[9585]=60;
dp[9586]=36;
dp[9587]=33;
dp[9588]=18;
dp[9589]=60;
dp[9590]=12;
dp[9591]=30;
dp[9592]=0;
dp[9593]=60;
dp[9594]=18;
dp[9595]=90;
dp[9596]=30;
dp[9597]=54;
dp[9598]=0;
dp[9599]=36;
dp[9600]=1;
dp[9601]=78;
dp[9602]=27;
dp[9603]=84;
dp[9604]=30;
dp[9605]=18;
dp[9606]=15;
dp[9607]=102;
dp[9608]=9;
dp[9609]=27;
dp[9610]=30;
dp[9611]=24;
dp[9612]=57;
dp[9613]=90;
dp[9614]=0;
dp[9615]=42;
dp[9616]=9;
dp[9617]=48;
dp[9618]=42;
dp[9619]=42;
dp[9620]=12;
dp[9621]=72;
dp[9622]=27;
dp[9623]=48;
dp[9624]=9;
dp[9625]=108;
dp[9626]=18;
dp[9627]=48;
dp[9628]=48;
dp[9629]=18;
dp[9630]=0;
dp[9631]=84;
dp[9632]=6;
dp[9633]=66;
dp[9634]=24;
dp[9635]=48;
dp[9636]=21;
dp[9637]=114;
dp[9638]=6;
dp[9639]=78;
dp[9640]=24;
dp[9641]=30;
dp[9642]=30;
dp[9643]=42;
dp[9644]=18;
dp[9645]=60;
dp[9646]=0;
dp[9647]=18;
dp[9648]=12;
dp[9649]=63;
dp[9650]=9;
dp[9651]=51;
dp[9652]=66;
dp[9653]=48;
dp[9654]=15;
dp[9655]=54;
dp[9656]=0;
dp[9657]=66;
dp[9658]=60;
dp[9659]=36;
dp[9660]=18;
dp[9661]=48;
dp[9662]=0;
dp[9663]=66;
dp[9664]=6;
dp[9665]=36;
dp[9666]=30;
dp[9667]=96;
dp[9668]=9;
dp[9669]=36;
dp[9670]=30;
dp[9671]=30;
dp[9672]=24;
dp[9673]=93;
dp[9674]=24;
dp[9675]=72;
dp[9676]=24;
dp[9677]=66;
dp[9678]=0;
dp[9679]=60;
dp[9680]=24;
dp[9681]=48;
dp[9682]=30;
dp[9683]=24;
dp[9684]=30;
dp[9685]=72;
dp[9686]=6;
dp[9687]=60;
dp[9688]=12;
dp[9689]=30;
dp[9690]=12;
dp[9691]=93;
dp[9692]=18;
dp[9693]=72;
dp[9694]=0;
dp[9695]=30;
dp[9696]=0;
dp[9697]=81;
dp[9698]=30;
dp[9699]=36;
dp[9700]=48;
dp[9701]=36;
dp[9702]=30;
dp[9703]=90;
dp[9704]=6;
dp[9705]=54;
dp[9706]=24;
dp[9707]=57;
dp[9708]=24;
dp[9709]=36;
dp[9710]=0;
dp[9711]=54;
dp[9712]=18;
dp[9713]=36;
dp[9714]=24;
dp[9715]=78;
dp[9716]=18;
dp[9717]=72;
dp[9718]=33;
dp[9719]=12;
dp[9720]=0;
dp[9721]=51;
dp[9722]=30;
dp[9723]=48;
dp[9724]=24;
dp[9725]=42;
dp[9726]=0;
dp[9727]=90;
dp[9728]=3;
dp[9729]=78;
dp[9730]=30;
dp[9731]=30;
dp[9732]=27;
dp[9733]=138;
dp[9734]=6;
dp[9735]=30;
dp[9736]=18;
dp[9737]=36;
dp[9738]=24;
dp[9739]=75;
dp[9740]=24;
dp[9741]=12;
dp[9742]=0;
dp[9743]=54;
dp[9744]=12;
dp[9745]=42;
dp[9746]=18;
dp[9747]=84;
dp[9748]=36;
dp[9749]=30;
dp[9750]=18;
dp[9751]=66;
dp[9752]=6;
dp[9753]=45;
dp[9754]=36;
dp[9755]=36;
dp[9756]=48;
dp[9757]=114;
dp[9758]=0;
dp[9759]=24;
dp[9760]=6;
dp[9761]=30;
dp[9762]=21;
dp[9763]=108;
dp[9764]=15;
dp[9765]=48;
dp[9766]=18;
dp[9767]=36;
dp[9768]=18;
dp[9769]=57;
dp[9770]=24;
dp[9771]=63;
dp[9772]=42;
dp[9773]=54;
dp[9774]=0;
dp[9775]=78;
dp[9776]=6;
dp[9777]=81;
dp[9778]=36;
dp[9779]=18;
dp[9780]=24;
dp[9781]=42;
dp[9782]=18;
dp[9783]=120;
dp[9784]=0;
dp[9785]=24;
dp[9786]=24;
dp[9787]=66;
dp[9788]=12;
dp[9789]=54;
dp[9790]=0;
dp[9791]=48;
dp[9792]=12;
dp[9793]=66;
dp[9794]=18;
dp[9795]=42;
dp[9796]=36;
dp[9797]=48;
dp[9798]=18;
dp[9799]=72;
dp[9800]=6;
dp[9801]=48;
dp[9802]=48;
dp[9803]=33;
dp[9804]=6;
dp[9805]=102;
dp[9806]=0;
dp[9807]=54;
dp[9808]=24;
dp[9809]=39;
dp[9810]=54;
dp[9811]=60;
dp[9812]=12;
dp[9813]=90;
dp[9814]=18;
dp[9815]=36;
dp[9816]=3;
dp[9817]=111;
dp[9818]=24;
dp[9819]=51;
dp[9820]=48;
dp[9821]=42;
dp[9822]=0;
dp[9823]=90;
dp[9824]=0;
dp[9825]=45;
dp[9826]=36;
dp[9827]=54;
dp[9828]=48;
dp[9829]=54;
dp[9830]=24;
dp[9831]=18;
dp[9832]=18;
dp[9833]=51;
dp[9834]=18;
dp[9835]=72;
dp[9836]=0;
dp[9837]=54;
dp[9838]=0;
dp[9839]=18;
dp[9840]=12;
dp[9841]=54;
dp[9842]=36;
dp[9843]=57;
dp[9844]=18;
dp[9845]=42;
dp[9846]=18;
dp[9847]=120;
dp[9848]=0;
dp[9849]=63;
dp[9850]=42;
dp[9851]=27;
dp[9852]=36;
dp[9853]=48;
dp[9854]=0;
dp[9855]=54;
dp[9856]=6;
dp[9857]=39;
dp[9858]=30;
dp[9859]=81;
dp[9860]=18;
dp[9861]=72;
dp[9862]=33;
dp[9863]=54;
dp[9864]=9;
dp[9865]=72;
dp[9866]=12;
dp[9867]=54;
dp[9868]=54;
dp[9869]=24;
dp[9870]=0;
dp[9871]=54;
dp[9872]=15;
dp[9873]=75;
dp[9874]=24;
dp[9875]=60;
dp[9876]=12;
dp[9877]=78;
dp[9878]=6;
dp[9879]=30;
dp[9880]=12;
dp[9881]=39;
dp[9882]=54;
dp[9883]=72;
dp[9884]=6;
dp[9885]=54;
dp[9886]=0;
dp[9887]=72;
dp[9888]=6;
dp[9889]=78;
dp[9890]=12;
dp[9891]=54;
dp[9892]=39;
dp[9893]=30;
dp[9894]=15;
dp[9895]=48;
dp[9896]=6;
dp[9897]=57;
dp[9898]=48;
dp[9899]=18;
dp[9900]=24;
dp[9901]=90;
dp[9902]=0;
dp[9903]=90;
dp[9904]=18;
dp[9905]=42;
dp[9906]=24;
dp[9907]=39;
dp[9908]=42;
dp[9909]=24;
dp[9910]=30;
dp[9911]=42;
dp[9912]=0;
dp[9913]=84;
dp[9914]=6;
dp[9915]=66;
dp[9916]=30;
dp[9917]=30;
dp[9918]=0;
dp[9919]=30;
dp[9920]=0;
dp[9921]=27;
dp[9922]=42;
dp[9923]=39;
dp[9924]=33;
dp[9925]=90;
dp[9926]=24;
dp[9927]=84;
dp[9928]=18;
dp[9929]=51;
dp[9930]=36;
dp[9931]=69;
dp[9932]=24;
dp[9933]=54;
dp[9934]=0;
dp[9935]=42;
dp[9936]=18;
dp[9937]=87;
dp[9938]=33;
dp[9939]=51;
dp[9940]=18;
dp[9941]=42;
dp[9942]=9;
dp[9943]=126;
dp[9944]=9;
dp[9945]=84;
dp[9946]=36;
dp[9947]=66;
dp[9948]=18;
dp[9949]=54;
dp[9950]=0;
dp[9951]=36;
dp[9952]=0;
dp[9953]=66;
dp[9954]=12;
dp[9955]=48;
dp[9956]=15;
dp[9957]=54;
dp[9958]=30;
dp[9959]=18;
dp[9960]=18;
dp[9961]=60;
dp[9962]=18;
dp[9963]=96;
dp[9964]=54;
dp[9965]=42;
dp[9966]=0;
dp[9967]=102;
dp[9968]=0;
dp[9969]=27;
dp[9970]=36;
dp[9971]=30;
dp[9972]=36;
dp[9973]=108;
dp[9974]=15;
dp[9975]=54;
dp[9976]=0;
dp[9977]=24;
dp[9978]=36;
dp[9979]=60;
dp[9980]=24;
dp[9981]=66;
dp[9982]=0;
dp[9983]=30;
dp[9984]=0;
dp[9985]=54;
dp[9986]=15;
dp[9987]=75;
dp[9988]=48;
dp[9989]=36;
dp[9990]=18;
dp[9991]=48;
dp[9992]=24;
dp[9993]=36;
dp[9994]=36;
dp[9995]=54;
dp[9996]=15;
dp[9997]=108;
dp[9998]=0;
dp[9999]=84;
dp[10000]=18;
    cin>>n;
    repu(i,1,n)
    {
        cout<<dp[i]<<endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1, tt=1;
    // cin>>t;
    while(tt<=t)
    {
        // cout<<"Case #"<<tt<<": ";
        always_ignore_function_name();
        tt++;
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3800