#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define int ll
#define endl "\n"
#define all( x ) x.begin(), x.end()
#define rev_all( x ) x.rbegin(), x.rend()
#define fast ios::sync_with_stdio(0);cin.tie(0);

typedef unsigned long long ull;

const int mod = 1e9 + 7;
const int inf = 1e12 + 5;
const long double PI = 3.141592653589793;

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

Measured memory_bytes: 3816