#include<bits/stdc++.h>
using namespace std;

/*
MOMMMMMOMOBMMMBMGMBMBMBMMMBM  iivvYuVoqXPPENGGOGMMMOMOBMBkkqMOBGJuPkkVZBkiBBBMONNqEGOOMGOMMMMONoLrrrrrriiii  BBMOGMGOOMOOOMOOOOOMMPjIFSXXBB   irISVJkP
MMOMOMOMOMOMOMOMOGOMMMMMMMMBu   irrLYYukkXSPqGGGZOGMGOGGSokOGOMSLVLuFGMBuJBBGGNNXqNGOOOMGMOONFYriiiiiiii    iBMMGOOOGOGGGMGOGOGOMOJJuFVFFBP   iuLirFkN
OGOOMOMOMOMOMOMOMOGOMOMOMOMMBk  iiivUuoVPXPPEEGGOGOOOGOGOEOMOONoPXINMMBBSZNrvVENGGOOMOMMMGGqIvviiiiiiiiiii  NBBOMOGGMOOGOOOOOGMOBkuoSFXkOMi iYXvivPPNU
OOOOOOGMOOGMOMOOOMOOOMOMOMOBBBS  iiivFoVSqNNPNSOGGOOGMOMMBMMMBYvNGOBGOSoSSvrJqEOOMOMMMMMOGPFLviiiiiiiiii  iVBBMOGOOGGOOOOMGMGOGMGFoIISIEBB ijIiiUEqENu
OOMOMOOGMOMGMOOOOOMOOGMOMMMMBBBo  iiivUUSSNNNXNNOGOEMOOGNGMOBZvJMOGkEXvVNEMMOOMOMOMOMOOMGNNuLriiiiiiii  iJqMBMMOMOONMOMOMGOGOOOONoUoXIPMBNiJr iUVPOZNP
GOOMGOGMGOGMOMGMOOOMOOOMOMOMOMBBo  iiivuUSVNEEEZEOOOGOGMGOOMBSvqOqSPNqEMkGMMMMOMOMOOGOMMZZSLiiiiiiii   jGMSMBMOMOMOMOOOMOOGOGOOOouuFkEGBBIri iqEPGEGEG
OGOGMGMOMOMOMOMOMOMOMMMOMOMOMMMBBS  iiivjUSSZZZZZNGGOGOOMOMMMLuGOqNPNNOMNGMOMOMMMOOOOOMGGXLiiiiiiii iLBBGYrMBOMOMOMOMGMOOGOOMOMXUukqOOMBBr  rNONNGGZGG
OOGOGMOMOMOMMMOMOMOMMMOMMMMMMMMMBBu  iiivuVNqqNGNEZOOOGMOMMBPvUOGZNZNZMBNGMMOMOMOOOOGMOGXjiiiiiii  uBBMIiijBMMMMMOOMOOGOGOOOOMOVjkqGOOOBk  iGONNNZEGOM
MGOGOOMOMOMOMOMOMOMOMMMOMOMMMMMMBBBu  iiirIkqXUqGqGGOOMGOMBBLiEOOGGZZGOMGPBMMOMOMGGZMMMNUrriiii  rBBMurvJvGMMOMGGOMOMOMGOOOOMMqjFPZZOGMMi ikGNNqNqZZZP
GOGMGMOMGMOOOMOMOMGMOMOMOMOMMMOMMBBBU  iiiLFXZuSGENOGOOZGBBG iPMGOGMOOGMOFGMMOGOGGEOOOqXJriiiiiikBELrLUuriOBMMOEGMOMOOOOGOGMOOkXPNEOGOBB  INXNNENENNkq
MOOGOOOOOGOOMGMOMOMGMOMOMOMOMOMMMMBMBu   iiLqEPSOZEZMOMEOBBv iNMMOMOOOOOBVFBMGOGOGMOMGEIYiiiivIGqrrrvvLriLBMMMMGMGMOMOOOOOOOONXkqEMGOOBk iNqNEZNZENkGq
OGOOGMGOOOOMOMOMGMOMOMOMOMOMGOMMMMMMBBj  iirINXPNGEGGMGOOBBi iNBGOGOGOGOMOrOMMGOGMOMMOPuriiivuLvvuJYLYLLiEBBMMOMOOOMMMOOGOGOOEkkNOGOGMBL LFNNZNGEZXMPi
MGOOOGOGOOMOOGOOMOMOMOMOMOMMMOMOMOMOMBBJ  iiLFkUPEGGOOMOMBM  iGMGGGGOGOGOMJvBOOGOOMMBNJi    vvYIkUUujJuvvMMMMGMMBMMOOGMGOOOGGSPNOGOGOOBriUVXNNENGGBVik
GOGMOOGMGMOMOOOMGMOMOOGMOMOMMMOOOMMMOBBBY  irUFISOZGOOGMMBE  iNMEGGOGGZGOMGiFBGGGMOBOJi   rPPFuUuUVIuYYruBMMOOOZEGGGOOGZOMGOPXNOGOOOOMBvioSNXNNGGBLiNB
OGOOOOOGMGMOMOMGMOOOMOMOMGMOMOMOGGMMMOMMBL iivSoVEGGOGOGMBX iiPZGGGZOGGZGGMViGMGMMMOFiiioMBZFuFVVVIUojjvGBBGZOONONGGMOOGOGOGEEOGGZGNGMMivuSPZNOMMiiOBM
OOOMGOGOOMOMOOOMGOMMOMOMOMOMOMOMOZGBMMMBBBL iivSUNGOOMOOMBF  iXGNMGGGOGOEGGBLrMBOMMqJJNBBZXPSPXqqSJjuuIEBBOqZMOBGOOMGOGOGOGGZGOOOOEZZBV iIqEEMBS iBBBJ
MGOOOGMOOOMOMOMGMOMOMOMMOOMOMOMOMMGEBMMMBMBY irvuXZqOGZGBBP iiNGGGOZGGOEGNGOBJrEMGGNMBBGNPNPqPqSPFkIkPOMBMNqMOMMGOMOOOOGOGOGOGGGOGGZOBv vVEEBMi UBBGi 
GOGMOOGMOMGMOMOMOMOMOMOMOOOMOMOMMMMZqMMMOMBBv rjvkSUIkkMMBNiiiUOEEZGEGNZNGGMMBXkZGEOGOZGNENNPNXkVPSEOMMMMOXOOOOOMMGOGMOOGOGGZGZGGGZOOBriSGGBU  MMBMq v
OGOOOOOGMOOGOOMOMOMOMOMOMOMOMMMOMMMMONOMMMBBBY rFIVvYuEMBBOiiiJGGNGEGENNGOMGOOMOOGOGGEZZGNZNEqPSXNGOMOMMMNGOMOMGMOOOMGOGOGOGGZOZGZGEMMYoOBBi JBBBBGOBB
OOOMGMGOOOGMOMOMOMOMOMOMOMOMMMMMMMMMMMNGMBMBBBJ iNXUYXGBMBBLiirGOGGGEGZOOMGOGMGOGOGGNZEGEGNENqPEEOMMOZOMZNGMOOOOOMOOOOGOOOGGGGEGZGZGMMFMBu iMBBBBV FBG
MGOOOGOOMOMOOGMOMOMOMOMOMOMOMOMMMMMOMMMNGMMMMBBu iqkFPOMMOBNiirUMOGNGGMGOGGGOGGGMGZZGEGEZZENNqGOMOMOENMOEGOOOGMOOGOGOGGGOGOGGZZGGGZEMMBO  kMBBBS   OBN
OGGMGOGOOOGOGOOMGMOMOMOMOMOMOOOMOMOMMMOBZZMBMBBBF iNkZGMMMMBviirPMMMOMOMGOGOGOGOGOZGZGZZEGEZGOOMOMGZZBMMGOOMGOOOGOGGZOGGGGGOEZGOGGEOMMr iBBBBZi   iBBq
OGOGOGOGMGOOOGOGMOOOMOMOMOMOMOMOMMMOMOMMMGNOBMBBBU iNGMOMNOBNiiiLZMMOOMGOOOGOGOGOGGZOEZEGGGGMOMMBMkkMMOOMOMOOGOOMOMOOGOGOGMGqZOGONGOBVrMBBBGi   iiVBMk
GGOOGOGOGOOMGOOMOOOMOMOMOMOMOMOMOMOMOMOMOBONGBMMBBS iOMBOqSOBLirrFOBOMOMGMGOGOGOGOGGZGZGGOOMOMMBOrrMOMGOOMOOGMOOOOGOGOGGZZEZqOGGGOOBFOBBMBi   iiiiMBOk
OZOGOGOGOGOOOGOOOOMOMOMOMOMOMOMOMOMOMMMOMMBMNZBMBMBq iBBBVkqBGrirvNGMOOGOGOGOGOGOGOGOGOGOGMMBBMXiiZZBMMGOOOOMGMGOGOZOZGZGEZNOGOOMMEvUBBMi   ivvirLBBOV
GGGOOMOOGOOOGOGOOMOOOMOMOMOMGMOMOMOMOMOMMMOMMGZMMMBBP rBBkNMBBkrrvjEGMOOGOGOGOGOGOOOOMOMOMBBOViiiPrBMMOOOMOOGOGOGOZOEGZOGGNGOMMMEouMBMi   ivvLrirPBBqu
OZOGMGOGOGOGOGOGMOMGOMOGMOMOMOMOMOMOMOOOMMMOMMOGMMBBBP oBNOMBBBUvvLFZGOOOGOGOGOGOGOOOGOOMMGSjrYuBiZBOOOGMGOOOGOGGZGZGGGGOZNMMZqSOMBj    iLoUYvvvvOBMqj
GGZOGOGOGOGOOMGOGMOOGOGOOMZMOMOOOOOMOMOMOMOMOMMMOMMBBBFiOBOMMBBBoYLoPGOOOOGOGOGOOOOOGOOMNSFXXBOMUNBMGGOMGOGMGOGOOOGGZGOOOZPNNOBBOr    ivjkSVJLvuUBBGVj
OGOZOGOGOGOGOOOGOGOOMOOGMMOGMGMOMOMOMOMOOGOOMOMMMMMOMBBVYBMOMMBBBFUUPNOGOGOGOGOGOOMOMOZSPEGGBNYGMBBOOGMOMOOGMOOOOOOGOZOEGNMBBBL     iiYuuLLvLvvrZBBNkU
OOOOGOGOGOGMGOGMGOGMOMGOOOOMOMOMOOGMOMGMOMOMOMOMMMOMMMMBFGMMMMMMBMXXPEGMGOGOGOGOOMOMGqkGZZZOGiqVBBOOGOGOOMOMOOGMGMGOGGOBBBBSi    iirvLJLvYLLvvrvBBOEqk
MGOGOGOGMGOGOOMOOOMGOOOOMOMOOOOOMGOOMOOOOOMOMOOOMMMOMOMMBNMMMMMMMMMkPZOGOGOGMGOGOOONNNZNENOOjMviBMOGMOMGMOOGOGGGGZOOBBBMFi    iiirvLLvvvLLuvvvvPBMOPBu
GOOOGOGGGOGOOMOOGOOOOOOMOMOMOOOMOMOMGMOMOOOOOMGGMMMMOMOMMMGMOBMMMMBMNZOMMMGOOBMMZGZGEOGOGOMEOZ BBOGMGMMMGOGOOOOMBBBBOFri    iiivLvrvvYvLvJLvJUIBBBGGBi
MGOGOGOZOGOGOGOGOOOGOGMOMOMOMOMOMOMOMGMOOOOOMOMZGMMOMOMOMMMMMOMMMMBMGSPqZGMOMOMGGGGGZEOMMOOGB NMBGOOMGOOMOMMMBBMMXjrirLi  iirvoVvrvrLvLLUVXSkoEBMOGBv 
OOGOOOGOGOZOGOOMGOGOOMOMGOGOOOOOGMOMGMGMOOOMOMOOqMMMOMOMOMMMMMMBMBBMNOZGNENOGkqOGOGOGGNVMMOBj jBMMOMMBBBBMGONXPFLLvuqqiiiiiLjoqVirvLvJukNqkPIVMBMBBP  
MOMOOGOOGGOGOGMGOGOGOOOGGGGGGGMOMOMOMOMOOOMGOOMOZXBMMMMOMMMMMMMMMOBONNGGGZGGMPEGOZOOMOBL ZBM   PBMMOZPqujuVVkXNPqNGZEviirrLVSFNLrrrLISqXqSVVINBBBNv i 
OOOOGOGOGOGOGOOOOGEOGMOMMMOMOMOOOOOOGMOOOMOMGMOOONZMOMOMMMOMMMOMMMMBNZGGGOGOONXMGOGOOOMGIMGirPiurrrLvuIPqGOGNGNZGOEEqvivrvIXZMVrrJUPNZNNkkFPOBBIi  iii
MGOGOOOGOGOGOGOGOGOOOGOOOOMOOOMOOOMGMOMGOOMOOOMOMMMOMOMOMOMMMMMMMOMMEqGGOGOGMPNOOGOGOGMMBBPiBBBMOOMMBBBOMGGZZEOOGNZqkvvrvvkqGurLPOBBBBMOBBBZXv   iiii 
MMOMOMGMOOGOGOGOGOGOGOOMOMOMGMOMOMOMOMOMOMGMOMOOGMMMOMOMOMMMOMOMOMMBONZGZGGMMOMBMMOMOMOMMMiOBMMMOMMOOOOGGOGOOMGONGEZuvrvjEOOFFMBBEuri   iii   iiiiiiii
MOMMMMOGMGOGOGOGOGOGOOOGOOMOOOMOMOMOMOMOOOMOOOMGOOMOMOMMMMMMMOMMMOMMBNZZOGGBOoXEBBBMBMMMBYIBBOOOOGOOOGOGOGOMMOOGMGMGLrLUMBBMGIvi     LBk    iiiiiiiii 
ZGOMMMOMOMOMGOGOGOGMGOGOOMOMOMMMOMOOOOGOOOGMOMOMGOGMMMMMMMOMMMMMOMMMMMPNNOOBi i  rXBMOBOqLBZLMGOGOGOGOZGZOGOGOGGGOMMoVNOXLi          ivBBq   iiiiiiiii
qkEZMMMOMOMOMGOGOGOGOGOGOGOOOGGEGGOOMOMOOGOOOGMOOGOGMOMOMOMMMOMOMMMOMMMNPNMuiPBVi i  vUijGN JMMGOGOGOGOOOOMOMOMBBBBMori         i i     SBBU  iiiiiiii
XVIVXOOMOMOMGOGOGOGOGOGOGMOOGMOMOOOMOMGMOMOMGMOMOOGOGOOBMMOMMMMMOMOMMMBMPEUuMBMBBBMjrjiSXBuEMMOMGOGOOMMMOMOMBBMBOUi      i iii   i       iBBBi  iiiiii
OkULuIEEOGMOOGOGMGOOOOMOMOOGMOMOMGMOOOMOOOMOMOMMMMMOOGGZOOMMMOMOMMMMMMMMBqPMBOMOMMBBBOBuBBBMMOMGMOOGMOBBBBBBMr  rii   iii   i     i        qBBo  iiiii
OONSIVkEZOOMOMOMGOOOGOOOOMOMGOGOOOGMOMGNSkqZZMONNOOMMMOMGMOMMMOOOMOMMMOMMBGOGOOMOOOMMBVkBMMMGMOMGZGBMBOEPGMBNuLILii      i   i     i        MBBo iiiii
JkMOOEGZOGMOOOMGOOMGOGMOOGMOOGMOOGOGMGZPXSPqENNIVFkXGZOMBBMMMMMOMMMMMMMMMMMGOGOOOGOMBGoBBMMOOOOGqOBOGENGBBBOkvi         i i   i             YBBB  iii 
 IBMOMOOGOOOOMOMGOGOOMOMOOOOOMOMGOOMOOENPNNGZqXNXPkXkNNNXqkGMMOBMMMMOMOMMMOMOMOMOOOMMPOBOMOOOMMMMMGOMBMNri                       i   i      vBBZ iiiii
iXBOMOOGGZGGOGOGGZOOMOOGMOMGMOOOOOMOOGGqEEOGGPNqNqNNZEZPXFSSNNMOBMMMBMOOMMMOMOMOMOMOOqBMMOMMBMMOOEkori                        i   i         iBBY iiii 
ZMOOGMGOZGZZZOZOGOZGGOOOOMGMOMGMGMGOOONNNOOONNNZNGEGEEqNPNPGGBMMMMGGMBMOOBMMOMOMMBMBGFMBMBBMGMOOGGqNkPNONFLLriiiiiii iiiii i i              iBBi iiiii
MOOOMOMOOEZNGZGOMOENGGMOMOOOMOMOMMMOOGENGOMNENZNZNGGENZNNNZNGGOGZXVoMMMGMMMMMOMMMMBBBBBBBBMGEkZOMOBOMOEPPXNXNNGqPUoviiiiiii i   i     i     iBB iiiiii
OOGOOMGOOOZOGOENNOOOGOGMOMOMOMOMOMOOGGEZGMGNEGEGEGGONZNEEGNqXZZOENFVNBGOMMMMMMOMMBBMBGJi irLrjGBGMMMMBEFJLiiiiiiiii      i i i i     i      iBE iiirrr
OGOOMOOOOGOOBZFuvkBBMMOGOGMGMOOOMOOOOZGGMOGZZZGGOGOEGZGNGZGXEEGGOOONPNMOOGMMMOMMBBj       rqGGqoqNZMGqMBBBBEYi  irrii iiiiiiiii   i   i     oBv irrvr 
GGGOGOGMOMBBGkoviJGBBBOOGGGOOOGOOMOOOGZOOOEGGGGGGOGOGGEENGGZXNNGZOOOGGGGGMOMMBBBBS         ZOYSMOIrviiFurBBv MjirivYriiiiiiiiiii ii         BB iivri  
OGOGOGOOMMMqYrLi iJXBBMMMGOOMGOOOOOGOZOGMGGEOGOOMGOGOGOZOGOZEXNNZZGGOZOGOOMOMMBBU     i i iPVJMMOEFjr iYirOJoNiiiiivLiiiiiiiiii   i        iBS iri  iL
GOOOGMMBBBUiiiriii iOBBBMMOOGOGMOMOOGOOMGGGGZOGOGGGOGOGOGGOONqPNNZNENZZGZOZMMMZYi      iiiivuEGGNPIoLiiruVPGui       i iiiii i i i i   i   OBiiri  ruN
OGOOMOGMBUiiiiiiii  LBBBBOMOOGOOMOMOMGMMOZOGOGOGGZOZOGGZOGMOZNNPNPZNZEZEGZGOBZjri     i i i irXGOGZXPkXuLii         i iiiiiiiii i     i   iMq r  iLFEj
OMMBMNvoPi iiiiiiriiiiXBMBMMOOOMOOGMGOGOGGGOGOGOZOOOGGZOGOGOGEqNqNqZNZNGEGEOOSLii i    i i     iJNqNPqIJvii  i iiiiiiiiiii i iii     i    BBi   ijFEU 
MMMMMjrriiiriiiirrLvi iJqMBMMOMOMGOOMGMOOGOGMGMGOGOGOGOGOGOOMGNqNPqqNNZNZNGMMoviiii              ivYuULiriiii   iiiiiiiii i i i   i i i  GBu  irukPv  
BGrvNqSr  iviiirviiri  iiYGBMMOMOOOOGMOOGOGOOOGOGOGOGGZOOOGOOMNNNNXNqNPNqEGMOIviii     i       i   iiviiiiiiiiiiiiiiiiiiiiii            UBO  irUSIi  v
BL  Ujii  ivJriirii i  ir LOBMMOMGOOMGMGOGOGOOOGOGOGOGOGOGMGOMOqGNNPqPNqNNOMOuriiii   i     i   iii iiiiiiiiiiiiiiiiiii i i   i i i    kBr  irUPL   UM
vi iPr ii  iJIiiiii  iiLviiPMBMMGOGMGMOOGOOOGOGOOOGOGOGOGOGOGMOONZXqPqXNPEOBZoii i           i   iiiiiiiiiiiiiiiiiiiiiii i iii   i   iBB  irLNPi  iEBB
rLIiov  iii ijvriiiiiiiivLvuMBMOOGOOOOMGOOMOOOOOOGOGOGOGMGOGMOMGGNEqqPNXqNMBELi i     i i i i     iiiiiiiiiiiiiiiiiiiii i iii i     vBN  roXGo   JMBBU
UFBJiLi  rrii iiiiiiiiiiiuuLNMOMOOGMOOOOGOOMGOGOOOGOGOGOOOGOOMMOMGNZNNPNqGMMVv       i   i   iii   iiiiiiiiiiiiiiiiiiiiiii i       GBi irNZOr  iIMOZv 
Siuv iLi iULi  iiiiiiiiiivjirSMGOGMOMGMOOOMOOGEGOGOGOGOGOGOOOOMNMMGNNqqNZEMEYi  i i     i     iirii iiiiiiiiiiiiiiiiiii i iii    rBZ  iJNONi  rNNXoi  
U  v  JBji iii iiiiiiiiiirr rMMOGGGMOMGOOOOMGGGOGOGOOMOOGOOOGMMqGBOZEGNENOOkiiii         i      rjriiiiiiiiiiiiiiiiiiiiiii i    MBr ivuGMS   oPXVvi  N
X  vF iGOi  iiiiiiiiiiii iiuBBMOOGOMMOOGMOMOOGMGOGOGOOOGOGOOMOOVBMBOEEZNNPPuiiiii     i   i     iLqUriiiiiiiiiiiiiiii iii     IMO  rvYNOv  ioSVjri  OB
Uu vBqi ii iiiiiii iiii  iBBMMOONEGBOMGOOOOMOOGOGOZGGOOOGOOMOBUoBBMBGZEZqIvLii i         i     irvjNNuiiiiiiiiiiii i i      vBBi irrrqX   rFJvri   BBF
rMSvBBri  iiiiiiiiiiii  iBBBMOZPNPLZBOOOMGMGOOOGOGGGOGOGOGMGMMkuBMMMBOGGNuLvi                  vuvriLSEYiiiiiiiii i       LBBu  rrivNY  ivuuLii  iBBO 
rNMGuiiriiiiiiiiiiiii  vMBMMGOEOBv OBMOMGOOOGOGOGOOOGOGOGOGOGMMLEBMMMBGEZkuoLi         iiiiiiiiiiiiiiivUYviiiiiiiii     vBBE  irrrUOi  iruLJri  iBMO  
UoZoi iiiiiiiiiiiiii  LBBOGOOGMBU SBMOMOMGOGOGOGOGOOOGOOMGOOOGBELBBMMMBNZGNFkui    iiiiiiiiiiiiiiiiii iiirriiiiii    ijMBBr iivrvkU  iiiJvrii  rBBO  i
ONLriiiiiiiiiiiiiii  vBBMMOOOMBq LBBOMOMOMOOOOGOGOOMGOGOOMOOOMOBuNBMMMMMGGGOOMMSvuOBOi iiiii iii iiiii i iiiiiiiii rFBBBBr XvLLuUi  iiirriii  jBBZ  rS
juviiiiiiiiiiiiiiii rBBMOOMGMMB iBBMMOOOOOMGOGMGOOOOOOOOOGMGOGMMGVBMMMMMBGGGMMBBBBMMMvi i iiiii iiiiiiiiii  iiiiiijZBBBBMiuNuLoi  iiiiiiiii  IBBG  LSZ
rrvrrrriiiiiiiiiii iMBMMOMOMMBi BBBMOMGMOOOOGOGOGOOOOOOOOOOOGMOMMPNBMBMBMMZGGGGMOPuqMNriiiiiiiiiiiiiiiiiiiii iiiirXMMBBBBIjSrv   iiiiiiiii  NBBE  ukXG
rivrrrrriiiiiiiii  OBBMOMOMMBN JBNPMMOMOMOOGMOOGOGOGMOOGOGMGOGMOMOIOBMMMMMMZOGGNEuiiEBorriiii   iiiiiiiii i   iiivqMMMBMBroi   iiiiiiiiii iNBBX  VPSEE
uLvvrrrrriiiiiiii iBBMOMMMMBBi BBXuBMOOMOOGOGMGOGOGOOMOOOMOOGOOOOBNFMBMMMMMMZGOMOOJvruriiiiii      i iiiiiiiiiiiruEBMBMBMNqv iiiiiiiiiii iMBBP  XNkGPN
uLJvvvrrrrriiiii  BBBOMOMOMMB VBGGNOBOOOOGMGOGOOMGOGOGOOMOMOOOMOOOBINBBMMMBMMZGGMBBMMNPoFuULvriivvvvLrvYVjvrriirvoOOMMBMMMOVviiiiiiiiii iBBBF iNNXPZOM
uJJjLLvvrrrriiii rBBMMOMOMMBv BMZOZjMBOMOMOOOOGMOOGMGOOOGMGMGOOOOOOMVOBMMMMBMMZGZGGBMBBBBBOBMGqkPSviiiiiiiiiiiirjZGMMMMBGOGIriiiiiiiii rBBBV rGNkNPOOB
PUuYjYYvvvvrviii EBMMOMOMMBMiUBOOGMLUMMOMOOOOOMGOGOOMGMOOOMOOOMGOGOMZSMMMMMOMMMGOGZNqNENEqFvrrii  i i i i iiiivLqOMOMMMMNOBFiiiiiiiii LMBBu vMZPPNMMBO
OGFoJJJJvLvrrriiiBBMOMOMOMMMXMOZZOOOLGMMOOGOOMOOOOOOOOOOOMOOGOGMOGOMMNNBMMMMOMOGGOGZoIkGPSVJii   iiiiiiiiiiiiivVZMOMOBMMqBBriiiiiiii uBBMu YMGNZZOBBGk
MOONIjJLYvYvrii uBBMMOMOMMMGOMMNZGOOOXGMMOOOOOOGOGMGMOMGMOMGOOOOOGOOMOqGBMMMMOMOZNOGOEZZZIqENuriiiiiiiiiiiiirrLVOOOOMMBOEBBiiiiiiiiikBBBv oMEZGMBGOEPk
OOMMqkuJLJvvrriiOBMMOMMMMBMGOMOOGGGOOGqOMMOOOOGMGOOMOOOOOMOOOOGOOMOMOMGqMBMMOMOBENPNqNNENqPkIJvriiiiiiiiiiiiirvVZOGMMBBONBEirLvvriiZBBBL kMNEGOBOOXXGM
MOMOMNkuYLLvvriiBBMOMOMMOOBPOOOGOEGOOOOGOGMMMGOOOGOOMGOOMOMOOOOGOOMOMOMEqMBMMOMMONNkVuFkILvrriiiiiiiiiiiiiiiiivIGOMBBMBEOBSivvYLrrZMBBL NMGZGOMZNPEGOZ
OMGMGOPkujLLvviUBMGMMMMMGBONGEZOGGEOMMOMZqqqOMOMOMOMOMGOOMOOOOGMOMOMOMOBqXBBMMMMOGNNVUuIjjriii iiiiiiiiiiiiiiivNMBBOvVBGOBLirvrrrOMBBLiEMGNMOMNXPOOOOG
OGMOGGGPIujLLrikBGOMMMMMOMOZOqGGOGGGOGOOOGGSSNBBBOMOMOMOMGMOMGOOMOMMMOMMBjIMMOMMMMONPjjuuuvriiiiiiiiiiiiiii iiUGBONuLEBNBBrivriiGBMMYrMOMOMOONEGOOOGOG
OOGOOGZGkVuJvriMBBOMOMMMMBEOGGGZEGGGNOGONMOOENUFMMBBOMOOOMOOOOOOOMMMOMMMMBiYOBMMMMMMZkYJJjLriiiiiiiii  i    ivNBOGNGGBMZBZirrirMBMGvrMMOOMOGXZGMGOGOZZ
MGMOONOGGkuLvriOBOMOMOOOMOqOOGONNGOEOGOEGOOGMMvJOUVMBBBOOGMOOOMOMOMOMOMOBBOioMBOMOMMBOESVJYviii i          iVMBMMOOGOMMEBSirrvMMMGESMMMMMGENMOMGOGGGOZ
OOOOZGGOZEIuLriMBMOMMMMMMMqOOOGGZOGGGMMZGMGMMViMGXLvLqMBMOGMOMOMMMOMMMMMMMBOIMMOOMMBMBBBMOXILrii        iYNBBBMMGMGOGBGGBVirLMMMGGGMOBMMGNNMGOGOGGGGGG
OGOGOOOGGNNVjrrGBOMOMOMGMOEOOGOZGGOEMOMZOZOOMLPONNZPYiuOOOMOMOMOMOMOMOMOMOMMBMMMMOMMMMBBBBBBBMMNXVPXEMBBBBBBBMMOOOOGOMOGBLiUMMMGGZOOEMMEEGOGOGOGOGGZOG
GMGOGOOOOGZONPPMMMOMMMZMMOVOEGZOOMENOMOGGOGMGMMGPqPEkEONPOMMOMOMOMOMOMOMOMMMOMMMOMOMOMMMMBBBBBBBBBMBBBBBBBBMOMOMOOOOOBGMBvuBMOZGGOOBMESGGOGOGOGOGOGGZZ
GPOOMOMOMGOMMMMGMGOOMOMOBMMOOGZEOOZZOGOGOGOOENMGGqNFXMGNMOMMMOMMMOMOMMMMMOMOMMMMMOMOMMBMBMBOOMBMBBBBBMBMMMMOMOMqOGOGOBOGMNMOOZOZMMBOGXGOOGOZGGOOOGGZGN
OOGOOMGMGOOMOMMMOMOMOMOMMNVBOOGGEOZOOOZOGOGOqMGZEGkPOGNMMMMMOMMMOMOMOMMMOMOMMMOMOMOMMMMBMMMMMBMMOMMMMMMMOMOMOMOOGOZOGNqOOMGGZOOMMOGNqOOMGGGGGOZGqGEZEP
MZOOMOMGGGOOMOOOOOMOMOMOBr BMGGGMNZOMOOGOZGEGOOGOGPUBOMOMOMMMOMOMOMOMOMMMOMMOOMMMMMOMMMMMMMMBMMMMMMMMMMOMOMOMOMGZZOGOEOOOGOGOOMMMGNEOOOGOGOGGEONNEGEZu
ZZGMMGqXFqOMOOGOOOOMOMOMMEVBGGGOGGGOOOGMOOEEOOGOOBvLMMOMOMMBMBMMOMMMOMOBMMOMOMOMOMOMMMOMMMOMMBMBMMMMMBMMMMOMGOGGEGNZGOGOGOGOOMOMNNEOGGZOEGEGEZEGZZPPkV
MGZPPVFIUSOMMGOGOGOOMOMOMMBMMOGEMOOGOGOOMOOqGZOGOqLGBMMOMGGZGGBMMOMMMOMNOMMMMOMOMMMMMOMMMMMMMOMMMOMMMMBMMOMOOGONENENGPGGGZGOMOMSFEGEGNNqqNNNZNNqENNkqF
GqFFVFUVuVNOOOOMOGGMOMOMOMMBMMGOGOOMGGGOOMZZGZNGEZMBMMOMMMGGqvvBBBMMOMMNPMOMMMMMOMOMMMOMOMOMOMMMOMMMOMMMOMGMGOGOZZNZPPEGNGOMMBEoXEqEXPkNPNNENZNGEGPNPS
ZVSVVUFVFINGMOMGOGOOOMMOMOMMBOMGGNMOMGGGGOEEOGGNEMBOMMMOMMMMBMkrMMOOMMMMMMMOMMMOMOMMMMMOMOMOMOMMMMMOMMMMMMMOMGGEEqENNNGNOMMMBMOVqqNSPSXXqXNNEqZEOENNEk
NFIXSPPZZGEOOMGOOMGOMMOMOMOMOMOOGGGOOMGOZGEGZOEOMMMMOMGMMMOMMBBi BMMOMOMOMOMMMOMOMMBMMMMOMOMOMOMMMMMMMMMOMOMGOGGqNPNPNNEOBMMMBEkXqkXkPqNXNqENENENZNGNX
XFNEGZMOMOOGGGMGMOMGOGMOMOMMMOMOOGGqGOOGOGZZOGOMMMMGMOMOMMMMMMBBiqBMMMMOMOMMMOOOMMMMMMMMMOMOMOMOMOMMMMMMMOMOOZGENXNXNNGOMMMMGGMkVVVFXkqqqqNqEqENNNEENF
NGOMGOGOGGGOGMOMOMOOGOOMOMMMMMOMMOGGZGZOOONGZOOMMMGGMMMMOMOMOMMBSuBMMMMMOMMMGOOMMMOMOMBBMMOMOMOMOMOMMMMMMMOMGGNEPqPqqZMBOMMMMMONoIokSqqNNZNEqNqENZNNPS
MGOGOGOOOGONNZMOOOOOGGOMMMMMMMMOMMOOMGZZGGOGMOBMMOOOMGMMMOMMMOMMBuBMBMMOMMBZGGMMMGOGOGXuMMMMMMMOMOMOMOMMMOMOOEZZNqNPEMBOMOBMMOMZXIkSXNGNNEZqqXNEZNEqNX
GGGOOMZZqNFVoXGMOOOMOGGMMMOMMMOMOMMMBBMONqZGMMMMMOOMOOOMOMOMOMOBBivBMMOMBMqEGMMMOOGOGOokMOGMMBMMOMOMOOOMMMMMGGZGqPkqGBMMMMMMMOMMEPkNNNNENZPNPqNEqNNENN
OEOZZPXIIUIuuIZOMOMOMGOOMOMOMMMMMMMBGiOBMEGOMOMMMNOMMOMOMOMOMMMMB  MBMMMOuXOMOOOMMMOONOMOGGNNNMMBMMOMOMMMMMMMGGNNkqZBMMMMMMMMMBGONNEGNGZENkqNNNNNqqNZq
OGZZSoouJouIVFkOMMGMGMOMMMOMOMMMOMMBZ rBMMOMOMOMOXZMMMOMOMMMMMOMBi BMMMGVNOBBBMBOMMMOMOOGOGGXjEGGMBBMMOMOMOMMMEEXkPMMMMMMMMMOMMMGGZGGOZZNZNZNENENNqZZN
MGONkjYYuoSkNNGGMOOOMMOOMMMOMOMMMOMMB  BBOMOMOMOMZOOMOMOMOMOMOMMBUvBBMOPGOMBGvBBMOMOMOMMMGOGNEMqqXNZBBBMMOMOMOONESZMMOMMMMMMMMMOOGGEGEGEGEZENNEqZNGNEk
GOGZPIvYFEGMOMGOGOOMOMOMMMMMOMOMOMMMBN PBMOMOMMMMONMMMOMMMMMOMOBZPBBMONGOMBBv MBMMMMMMOOGMOMOMGZNNkviGBBBBMMMMOGqXGBMMGMOMOMMMMGGGZZNGEGZGZZqNPNEZNNNX
OZMGONkVNOMGOGOGOGOOBMBOMOMMMMMMMMMMBB iBMMMMOMMMMNEMMMMMMMOMOBOIOBMOqGOMMMMOGiGBMMOMMMGOGGGMOZEZNVrrkGJuMBBBMBMZNMMMMMOOMMMMOBOOGGZGEGZGZZNNNENGNEPqV
GOGOOOZNFNGOGGZOOOOMGNEMMMMMOMMMOMOMMBY BBOMMMOMOMOOOMMMMMOMMBO uBMESZGMMMGOBu EBMOMOMOMMMOMOOGOOEJIGMPuivuNBBBBOBMMMMOMOMOMOMMBGOEGEGEGEZNENGGGEZPqqF
GGZSMGOkjjGGOGOMBOGFuvuZBOMOMOMOMMMOBBM jBBMMOMOMOMMMMMOMOMOMMMEBMqUEOBMOSNBBi BBOMOMOMOMOOGMGGEGZMBMNqFPJ iMEOOMGBMBMMMBMBMMMMOZGGZGZGZZNZNGEZNENNNNV
EGZZZOGZuLVMGOOZSoYLvvrPBMOOOMOMOMMMMBMi BBMMMMMOMOMOMMMOMOMOMMBMGSNOBMMZkNBB vBMMOMOMOOOMOMOOOGkOGOMOXPF iMkVVFi rBMMOMBBBBBBBGIOZGZZNGNZEGZGEEEEqNqX
OqGEEEOOSJVZMOEuvvvvvvvNBMMMMOMMMOMOMMBk kBMOOMOMMMOMMMOMOMMMOMMMZOOMMMNENqBO ZBMMMOMOMOMOMMMOOOMGuivMBOi NGqPkui rMGFIIXuiqBMMMENZEENNNEZGZZEZEZPNPNS
ZEEZEZGMqVVGOMZFLrvLJIFMMMMMOBMMMMOMOOMB  BMqOGOOMMMMMOOOMOMOMOMGOMBMOENGMkBF MBMMOMOMOOOMOOOMMMOMZViiYMYPMZPZNS  OBGPSSv  NMOZMEEqNXZNGNZNZNZEGEEPZqN
EPEZZNGOZVPOMOOEIvuFOOOMMOMOMOMMMOMOMMBMv ZMMOMMMOMMMOMOMOMMMOMOMOMOMGGOMOOBV BMMOMOOOOOMOMOOOMOMOMMMIi XBMGMOBOUSBGGNEPL iBBBMMMNqqNEGGGNGNGZGNZNZNEP
qqEGNGZMENPMOMOMENGMOONMOMMOOMOMMMOMOMMBM  BMMOMOMMMMMMMOMOMOMOMOMMMOOOMGMGMYiMBMMGMGMOMOOOOGMOMOMOMMBBMBMOMOMMBMBMMOMMMMMBBZEZMMEXNEGZZqGNGZZZOZGEZqP
NPEqZGMOVuEMMOOOMMMOZEEGMOMGOMMMMOMOOMMBBi qBMMMMOMMMOMMMOMOMOMMMMBMBOOOOGMUriBMMOMOOOMOMOMOMOMOOOMOMOMMMOOOMOOOBOMOOOOGMMGuLirOBNNNZEGNqGGZGZGEGNZqNX
kkPNNMOYiiXBOMGMMMOOGENMMMOMOMOOOMOMOMMBMG iBBMMOMOMOMOMMMOOOMMMMMOSMBOOGMMqiiMBOOOOOOGMOMOMOOOOGMOOOOOMGOOOGOGOGOGOGGGGEGEPVYjBBMEGZEEOGZENPZEEqNXqXX
SVqNGMNi  XBMOMGMOOGOqGOMMMGOOMOMMMOMOMOBBi GBMMMOMMMOMOMOMOMMMOOMBvNBMOMOBNriBMMOMOOGMOMOMOMGOOOOOOMOOGMOOGOGOGOGOGOGOGOZNZGZMNBOZNZZZEGEENNNENNqZNEk
SFqGGMui iMBOOOMGOGOZZGMOMMOEOOMMMOMZOMMBBS  BBBMMMMMMMMOMOMOBMMOBBIjBOOOMMGYiSBOMOMMMOMOMGMOOGMGMOMOOGOGOGMGOGOOOGGGOGOGqZO rkjMMEGEGEOZGNZNEGZZMOMMM
VSqNGNuirEBMMOOOOOOGGNOOMOOGMGOMMMMOZEMOBBB  XBMMOMOMOMMMOMMMuNBBMBGJOMOOOBGUirMMOOOMOOOMOMGOOOGMOOOOGOGMGOGOGOGMGOGOOMOGGBJiESoBMGGGZOGZNZGMMBMBBBOMO
VSqZGZFSGBMMOMOMGMOMGEGOGMOMOGOMOMMMGOOMMBBo  BBMMOMMMOMOMOBBkiOBBMBFNMMOMMOFL MBMOMGMOMOOOOOMOOOMOOGOGOOOGOGOGOGOGOGOGGGMZi MXkMBGOZGEZGOMBBBOOENVSoj
qkOOMOMMBMMMBMBMBMBMMGMOMGMOMGMOMOMMMGMMMMBB  FBBOMMMMMMMMMOBBviBBMBGFMOOOMGXNijBMMOMOOGMOMOOOOGOOOGOGOOMOOOOGGGGGOGMGGGMGN iGUJBMOGOGOEBBBMZXXUuLuoqN
NZGMMMBBMBMBOMMMBBBGPEMMMMOMOMGMMMOMOGOMOMMBu  BBBMMOMOMMMMMMBBijBMBMPGMOMOMXGJiBBMMMMOMOOOMGMGOGOOOGMGOOOOMGOGOGOGMOGOMGGXivULjMBGOZOOBBGIVFkXNPqqqqq
r rvvjJvUvrVqSPvvvv  vIMOOMOMOOOMOMMMZOGOOBMB  iBMMOMOMGGOMOMMBNiIMOBZNOMOMMZEOivMMOMOOGMOOGOOOGOGOGOGOGMGOGOGGGOGOZGGEUuuv vvrvMMOGGGBMv iVNNZNNPNNGG
*/

int a[100010];
int d[100010];
bool used[100010];
deque <int> q;

int main(){
	int n;
	cin>>n;
	int p=10%n;
	q.push_back(1);
	memset(d,-1,sizeof(d));
	d[1]=0;
	memset(used,false,sizeof(used));
	while (!q.empty()){
		int x=q.front();
		q.pop_front();
		if (x==0) break;
		if (used[x]) continue;
		used[x]=true;
		if (d[(x+1)%n]==-1||d[x]+1<d[(x+1)%n]){
			d[(x+1)%n]=d[x]+1;
			q.push_back((x+1)%n);
		}
		if (d[(x*p)%n]==-1||d[x]<d[(x*p)%n]) {
			d[(x*p)%n]=d[x];
			q.push_front((x*p)%n);
		}
	}
	cout<<d[0]+1<<endl;
//	for (int i=0;i<n;i++) cout<<d[i]<<" ";
	return 0;
}

Measured memory_bytes: 896