結果
| 問題 | No.262 面白くないビットすごろく |
| ユーザー |
 uwi
|
| 提出日時 | 2015-08-01 18:14:47 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 89 ms / 2,000 ms |
| コード長 | 51,461 bytes |
| コンパイル時間 | 4,152 ms |
| コンパイル使用メモリ | 81,616 KB |
| 実行使用メモリ | 50,096 KB |
| 最終ジャッジ日時 | 2023-09-25 00:21:58 |
| 合計ジャッジ時間 | 5,012 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 44 ms
49,120 KB |
| testcase_01 | AC | 88 ms
49,660 KB |
| testcase_02 | AC | 85 ms
50,096 KB |
| testcase_03 | AC | 89 ms
47,772 KB |
ソースコード
package q4xx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Q402B {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
long n = nl();
int ind = (int)(n>>>29);
long step = steps[ind] + 1;
long val = vals[ind];
while(val < n){
val += Long.bitCount(val);
step++;
}
if(val == n){
out.println(step);
}else{
out.println(-1);
}
}
long[] vals = {
1L,536870920L,1073741831L,1610612743L,2147483649L,2684354567L,3221225473L,3758096385L,4294967308L,4831838215L,5368709121L,5905580033L,6442450956L,6979321857L,7516192780L,8053063692L,8589934610L,9126805511L,9663676417L,10200547329L,10737418252L,11274289153L,11811160076L,12348030988L,12884901906L,13421772801L,13958643724L,14495514636L,15032385554L,15569256460L,16106127378L,16642998290L,17179869198L,17716740103L,18253611009L,18790481921L,19327352844L,19864223745L,20401094668L,20937965580L,21474836498L,22011707393L,22548578316L,23085449228L,23622320146L,24159191052L,24696061970L,25232932882L,25769803790L,26306674689L,26843545612L,27380416524L,27917287442L,28454158348L,28991029266L,29527900178L,30064771086L,30601641996L,31138512914L,31675383826L,32212254734L,32749125650L,33285996558L,33822867470L,34359738383L,34896609287L,35433480193L,35970351105L,36507222028L,37044092929L,37580963852L,38117834764L,38654705682L,39191576577L,39728447500L,40265318412L,40802189330L,41339060236L,41875931154L,42412802066L,42949672974L,43486543873L,44023414796L,44560285708L,45097156626L,45634027532L,46170898450L,46707769362L,47244640270L,47781511180L,48318382098L,48855253010L,49392123918L,49928994834L,50465865742L,51002736654L,51539607567L,52076478465L,52613349388L,53150220300L,53687091218L,54223962124L,54760833042L,55297703954L,55834574862L,56371445772L,56908316690L,57445187602L,57982058510L,58518929426L,59055800334L,59592671246L,60129542159L,60666413068L,61203283986L,61740154898L,62277025806L,62813896722L,63350767630L,63887638542L,64424509455L,64961380370L,65498251278L,66035122190L,66571993103L,67108864014L,67645734927L,68182605839L,68719476771L,69256347655L,69793218561L,70330089473L,70866960396L,71403831297L,71940702220L,72477573132L,73014444050L,73551314945L,74088185868L,74625056780L,75161927698L,75698798604L,76235669522L,76772540434L,77309411342L,77846282241L,78383153164L,78920024076L,79456894994L,79993765900L,80530636818L,81067507730L,81604378638L,82141249548L,82678120466L,83214991378L,83751862286L,84288733202L,84825604110L,85362475022L,85899345935L,86436216833L,86973087756L,87509958668L,88046829586L,88583700492L,89120571410L,89657442322L,90194313230L,90731184140L,91268055058L,91804925970L,92341796878L,92878667794L,93415538702L,93952409614L,94489280527L,95026151436L,95563022354L,96099893266L,96636764174L,97173635090L,97710505998L,98247376910L,98784247823L,99321118738L,99857989646L,100394860558L,100931731471L,101468602382L,102005473295L,102542344207L,103079215139L,103616086017L,104152956940L,104689827852L,105226698770L,105763569676L,106300440594L,106837311506L,107374182414L,107911053324L,108447924242L,108984795154L,109521666062L,110058536978L,110595407886L,111132278798L,111669149711L,112206020620L,112742891538L,113279762450L,113816633358L,114353504274L,114890375182L,115427246094L,115964117007L,116500987922L,117037858830L,117574729742L,118111600655L,118648471566L,119185342479L,119722213391L,120259084323L,120795955212L,121332826130L,121869697042L,122406567950L,122943438866L,123480309774L,124017180686L,124554051599L,125090922514L,125627793422L,126164664334L,126701535247L,127238406158L,127775277071L,128312147983L,128849018915L,129385889810L,129922760718L,130459631630L,130996502543L,131533373454L,132070244367L,132607115279L,133143986211L,133680857102L,134217728015L,134754598927L,135291469859L,135828340751L,136365211683L,136902082595L,137438953477L,137975824391L,138512695297L,139049566209L,139586437132L,140123308033L,140660178956L,141197049868L,141733920786L,142270791681L,142807662604L,143344533516L,143881404434L,144418275340L,144955146258L,145492017170L,146028888078L,146565758977L,147102629900L,147639500812L,148176371730L,148713242636L,149250113554L,149786984466L,150323855374L,150860726284L,151397597202L,151934468114L,152471339022L,153008209938L,153545080846L,154081951758L,154618822671L,155155693569L,155692564492L,156229435404L,156766306322L,157303177228L,157840048146L,158376919058L,158913789966L,159450660876L,159987531794L,160524402706L,161061273614L,161598144530L,162135015438L,162671886350L,163208757263L,163745628172L,164282499090L,164819370002L,165356240910L,165893111826L,166429982734L,166966853646L,167503724559L,168040595474L,168577466382L,169114337294L,169651208207L,170188079118L,170724950031L,171261820943L,171798691875L,172335562753L,172872433676L,173409304588L,173946175506L,174483046412L,175019917330L,175556788242L,176093659150L,176630530060L,177167400978L,177704271890L,178241142798L,178778013714L,179314884622L,179851755534L,180388626447L,180925497356L,181462368274L,181999239186L,182536110094L,183072981010L,183609851918L,184146722830L,184683593743L,185220464658L,185757335566L,186294206478L,186831077391L,187367948302L,187904819215L,188441690127L,188978561059L,189515431948L,190052302866L,190589173778L,191126044686L,191662915602L,192199786510L,192736657422L,193273528335L,193810399250L,194347270158L,194884141070L,195421011983L,195957882894L,196494753807L,197031624719L,197568495651L,198105366546L,198642237454L,199179108366L,199715979279L,200252850190L,200789721103L,201326592015L,201863462947L,202400333838L,202937204751L,203474075663L,204010946595L,204547817487L,205084688419L,205621559331L,206158430213L,206695301121L,207232172044L,207769042956L,208305913874L,208842784780L,209379655698L,209916526610L,210453397518L,210990268428L,211527139346L,212064010258L,212600881166L,213137752082L,213674622990L,214211493902L,214748364815L,215285235724L,215822106642L,216358977554L,216895848462L,217432719378L,217969590286L,218506461198L,219043332111L,219580203026L,220117073934L,220653944846L,221190815759L,221727686670L,222264557583L,222801428495L,223338299427L,223875170316L,224412041234L,224948912146L,225485783054L,226022653970L,226559524878L,227096395790L,227633266703L,228170137618L,228707008526L,229243879438L,229780750351L,230317621262L,230854492175L,231391363087L,231928234019L,232465104914L,233001975822L,233538846734L,234075717647L,234612588558L,235149459471L,235686330383L,236223201315L,236760072206L,237296943119L,237833814031L,238370684963L,238907555855L,239444426787L,239981297699L,240518168581L,241055039500L,241591910418L,242128781330L,242665652238L,243202523154L,243739394062L,244276264974L,244813135887L,245350006802L,245886877710L,246423748622L,246960619535L,247497490446L,248034361359L,248571232271L,249108103203L,249644974098L,250181845006L,250718715918L,251255586831L,251792457742L,252329328655L,252866199567L,253403070499L,253939941390L,254476812303L,255013683215L,255550554147L,256087425039L,256624295971L,257161166883L,257698037765L,258234908690L,258771779598L,259308650510L,259845521423L,260382392334L,260919263247L,261456134159L,261993005091L,262529875982L,263066746895L,263603617807L,264140488739L,264677359631L,265214230563L,265751101475L,266287972357L,266824843278L,267361714191L,267898585103L,268435456035L,268972326927L,269509197859L,270046068771L,270582939653L,271119810575L,271656681507L,272193552419L,272730423301L,273267294243L,273804165125L,274341036037L,274877906964L,275414777863L,275951648769L,276488519681L,277025390604L,277562261505L,278099132428L,278636003340L,279172874258L,279709745153L,280246616076L,280783486988L,281320357906L,281857228812L,282394099730L,282930970642L,283467841550L,284004712449L,284541583372L,285078454284L,285615325202L,286152196108L,286689067026L,287225937938L,287762808846L,288299679756L,288836550674L,289373421586L,289910292494L,290447163410L,290984034318L,291520905230L,292057776143L,292594647041L,293131517964L,293668388876L,294205259794L,294742130700L,295279001618L,295815872530L,296352743438L,296889614348L,297426485266L,297963356178L,298500227086L,299037098002L,299573968910L,300110839822L,300647710735L,301184581644L,301721452562L,302258323474L,302795194382L,303332065298L,303868936206L,304405807118L,304942678031L,305479548946L,306016419854L,306553290766L,307090161679L,307627032590L,308163903503L,308700774415L,309237645347L,309774516225L,310311387148L,310848258060L,311385128978L,311921999884L,312458870802L,312995741714L,313532612622L,314069483532L,314606354450L,315143225362L,315680096270L,316216967186L,316753838094L,317290709006L,317827579919L,318364450828L,318901321746L,319438192658L,319975063566L,320511934482L,321048805390L,321585676302L,322122547215L,322659418130L,323196289038L,323733159950L,324270030863L,324806901774L,325343772687L,325880643599L,326417514531L,326954385420L,327491256338L,328028127250L,328564998158L,329101869074L,329638739982L,330175610894L,330712481807L,331249352722L,331786223630L,332323094542L,332859965455L,333396836366L,333933707279L,334470578191L,335007449123L,335544320018L,336081190926L,336618061838L,337154932751L,337691803662L,338228674575L,338765545487L,339302416419L,339839287310L,340376158223L,340913029135L,341449900067L,341986770959L,342523641891L,343060512803L,343597383685L,344134254593L,344671125516L,345207996428L,345744867346L,346281738252L,346818609170L,347355480082L,347892350990L,348429221900L,348966092818L,349502963730L,350039834638L,350576705554L,351113576462L,351650447374L,352187318287L,352724189196L,353261060114L,353797931026L,354334801934L,354871672850L,355408543758L,355945414670L,356482285583L,357019156498L,357556027406L,358092898318L,358629769231L,359166640142L,359703511055L,360240381967L,360777252899L,361314123788L,361850994706L,362387865618L,362924736526L,363461607442L,363998478350L,364535349262L,365072220175L,365609091090L,366145961998L,366682832910L,367219703823L,367756574734L,368293445647L,368830316559L,369367187491L,369904058386L,370440929294L,370977800206L,371514671119L,372051542030L,372588412943L,373125283855L,373662154787L,374199025678L,374735896591L,375272767503L,375809638435L,376346509327L,376883380259L,377420251171L,377957122053L,378493992972L,379030863890L,379567734802L,380104605710L,380641476626L,381178347534L,381715218446L,382252089359L,382788960274L,383325831182L,383862702094L,384399573007L,384936443918L,385473314831L,386010185743L,386547056675L,387083927570L,387620798478L,388157669390L,388694540303L,389231411214L,389768282127L,390305153039L,390842023971L,391378894862L,391915765775L,392452636687L,392989507619L,393526378511L,394063249443L,394600120355L,395136991237L,395673862162L,396210733070L,396747603982L,397284474895L,397821345806L,398358216719L,398895087631L,399431958563L,399968829454L,400505700367L,401042571279L,401579442211L,402116313103L,402653184035L,403190054947L,403726925829L,404263796750L,404800667663L,405337538575L,405874409507L,406411280399L,406948151331L,407485022243L,408021893125L,408558764047L,409095634979L,409632505891L,410169376773L,410706247715L,411243118597L,411779989509L,412316860436L,412853731329L,413390602252L,413927473164L,414464344082L,415001214988L,415538085906L,416074956818L,416611827726L,417148698636L,417685569554L,418222440466L,418759311374L,419296182290L,419833053198L,420369924110L,420906795023L,421443665932L,421980536850L,422517407762L,423054278670L,423591149586L,424128020494L,424664891406L,425201762319L,425738633234L,426275504142L,426812375054L,427349245967L,427886116878L,428422987791L,428959858703L,429496729635L,430033600524L,430570471442L,431107342354L,431644213262L,432181084178L,432717955086L,433254825998L,433791696911L,434328567826L,434865438734L,435402309646L,435939180559L,436476051470L,437012922383L,437549793295L,438086664227L,438623535122L,439160406030L,439697276942L,440234147855L,440771018766L,441307889679L,441844760591L,442381631523L,442918502414L,443455373327L,443992244239L,444529115171L,445065986063L,445602856995L,446139727907L,446676598789L,447213469708L,447750340626L,448287211538L,448824082446L,449360953362L,449897824270L,450434695182L,450971566095L,451508437010L,452045307918L,452582178830L,453119049743L,453655920654L,454192791567L,454729662479L,455266533411L,455803404306L,456340275214L,456877146126L,457414017039L,457950887950L,458487758863L,459024629775L,459561500707L,460098371598L,460635242511L,461172113423L,461708984355L,462245855247L,462782726179L,463319597091L,463856467973L,464393338898L,464930209806L,465467080718L,466003951631L,466540822542L,467077693455L,467614564367L,468151435299L,468688306190L,469225177103L,469762048015L,470298918947L,470835789839L,471372660771L,471909531683L,472446402565L,472983273486L,473520144399L,474057015311L,474593886243L,475130757135L,475667628067L,476204498979L,476741369861L,477278240783L,477815111715L,478351982627L,478888853509L,479425724451L,479962595333L,480499466245L,481036337172L,481573208076L,482110078994L,482646949906L,483183820814L,483720691730L,484257562638L,484794433550L,485331304463L,485868175378L,486405046286L,486941917198L,487478788111L,488015659022L,488552529935L,489089400847L,489626271779L,490163142674L,490700013582L,491236884494L,491773755407L,492310626318L,492847497231L,493384368143L,493921239075L,494458109966L,494994980879L,495531851791L,496068722723L,496605593615L,497142464547L,497679335459L,498216206341L,498753077266L,499289948174L,499826819086L,500363689999L,500900560910L,501437431823L,501974302735L,502511173667L,503048044558L,503584915471L,504121786383L,504658657315L,505195528207L,505732399139L,506269270051L,506806140933L,507343011854L,507879882767L,508416753679L,508953624611L,509490495503L,510027366435L,510564237347L,511101108229L,511637979151L,512174850083L,512711720995L,513248591877L,513785462819L,514322333701L,514859204613L,515396075540L,515932946450L,516469817358L,517006688270L,517543559183L,518080430094L,518617301007L,519154171919L,519691042851L,520227913742L,520764784655L,521301655567L,521838526499L,522375397391L,522912268323L,523449139235L,523986010117L,524522881038L,525059751951L,525596622863L,526133493795L,526670364687L,527207235619L,527744106531L,528280977413L,528817848335L,529354719267L,529891590179L,530428461061L,530965332003L,531502202885L,532039073797L,532575944724L,533112815630L,533649686543L,534186557455L,534723428387L,535260299279L,535797170211L,536334041123L,536870912005L,537407782927L,537944653859L,538481524771L,539018395653L,539555266595L,540092137477L,540629008389L,541165879316L,541702750223L,542239621155L,542776492067L,543313362949L,543850233891L,544387104773L,544923975685L,545460846612L,545997717539L,546534588421L,547071459333L,547608330260L,548145201157L,548682072084L,549218942996L,549755813924L,550292684807L,550829555713L,551366426625L,551903297548L,552440168449L,552977039372L,553513910284L,554050781202L,554587652097L,555124523020L,555661393932L,556198264850L,556735135756L,557272006674L,557808877586L,558345748494L,558882619393L,559419490316L,559956361228L,560493232146L,561030103052L,561566973970L,562103844882L,562640715790L,563177586700L,563714457618L,564251328530L,564788199438L,565325070354L,565861941262L,566398812174L,566935683087L,567472553985L,568009424908L,568546295820L,569083166738L,569620037644L,570156908562L,570693779474L,571230650382L,571767521292L,572304392210L,572841263122L,573378134030L,573915004946L,574451875854L,574988746766L,575525617679L,576062488588L,576599359506L,577136230418L,577673101326L,578209972242L,578746843150L,579283714062L,579820584975L,580357455890L,580894326798L,581431197710L,581968068623L,582504939534L,583041810447L,583578681359L,584115552291L,584652423169L,585189294092L,585726165004L,586263035922L,586799906828L,587336777746L,587873648658L,588410519566L,588947390476L,589484261394L,590021132306L,590558003214L,591094874130L,591631745038L,592168615950L,592705486863L,593242357772L,593779228690L,594316099602L,594852970510L,595389841426L,595926712334L,596463583246L,597000454159L,597537325074L,598074195982L,598611066894L,599147937807L,599684808718L,600221679631L,600758550543L,601295421475L,601832292364L,602369163282L,602906034194L,603442905102L,603979776018L,604516646926L,605053517838L,605590388751L,606127259666L,606664130574L,607201001486L,607737872399L,608274743310L,608811614223L,609348485135L,609885356067L,610422226962L,610959097870L,611495968782L,612032839695L,612569710606L,613106581519L,613643452431L,614180323363L,614717194254L,615254065167L,615790936079L,616327807011L,616864677903L,617401548835L,617938419747L,618475290629L,619012161537L,619549032460L,620085903372L,620622774290L,621159645196L,621696516114L,622233387026L,622770257934L,623307128844L,623843999762L,624380870674L,624917741582L,625454612498L,625991483406L,626528354318L,627065225231L,627602096140L,628138967058L,628675837970L,629212708878L,629749579794L,630286450702L,630823321614L,631360192527L,631897063442L,632433934350L,632970805262L,633507676175L,634044547086L,634581417999L,635118288911L,635655159843L,636192030732L,636728901650L,637265772562L,637802643470L,638339514386L,638876385294L,639413256206L,639950127119L,640486998034L,641023868942L,641560739854L,642097610767L,642634481678L,643171352591L,643708223503L,644245094435L,644781965330L,645318836238L,645855707150L,646392578063L,646929448974L,647466319887L,648003190799L,648540061731L,649076932622L,649613803535L,650150674447L,650687545379L,651224416271L,651761287203L,652298158115L,652835028997L,653371899916L,653908770834L,654445641746L,654982512654L,655519383570L,656056254478L,656593125390L,657129996303L,657666867218L,658203738126L,658740609038L,659277479951L,659814350862L,660351221775L,660888092687L,661424963619L,661961834514L,662498705422L,663035576334L,663572447247L,664109318158L,664646189071L,665183059983L,665719930915L,666256801806L,666793672719L,667330543631L,667867414563L,668404285455L,668941156387L,669478027299L,670014898181L,670551769106L,671088640014L,671625510926L,672162381839L,672699252750L,673236123663L,673772994575L,674309865507L,674846736398L,675383607311L,675920478223L,676457349155L,676994220047L,677531090979L,678067961891L,678604832773L,679141703694L,679678574607L,680215445519L,680752316451L,681289187343L,681826058275L,682362929187L,682899800069L,683436670991L,683973541923L,684510412835L,685047283717L,685584154659L,686121025541L,686657896453L,687194767380L,687731638273L,688268509196L,688805380108L,689342251026L,689879121932L,690415992850L,690952863762L,691489734670L,692026605580L,692563476498L,693100347410L,693637218318L,694174089234L,694710960142L,695247831054L,695784701967L,696321572876L,696858443794L,697395314706L,697932185614L,698469056530L,699005927438L,699542798350L,700079669263L,700616540178L,701153411086L,701690281998L,702227152911L,702764023822L,703300894735L,703837765647L,704374636579L,704911507468L,705448378386L,705985249298L,706522120206L,707058991122L,707595862030L,708132732942L,708669603855L,709206474770L,709743345678L,710280216590L,710817087503L,711353958414L,711890829327L,712427700239L,712964571171L,713501442066L,714038312974L,714575183886L,715112054799L,715648925710L,716185796623L,716722667535L,717259538467L,717796409358L,718333280271L,718870151183L,719407022115L,719943893007L,720480763939L,721017634851L,721554505733L,722091376652L,722628247570L,723165118482L,723701989390L,724238860306L,724775731214L,725312602126L,725849473039L,726386343954L,726923214862L,727460085774L,727996956687L,728533827598L,729070698511L,729607569423L,730144440355L,730681311250L,731218182158L,731755053070L,732291923983L,732828794894L,733365665807L,733902536719L,734439407651L,734976278542L,735513149455L,736050020367L,736586891299L,737123762191L,737660633123L,738197504035L,738734374917L,739271245842L,739808116750L,740344987662L,740881858575L,741418729486L,741955600399L,742492471311L,743029342243L,743566213134L,744103084047L,744639954959L,745176825891L,745713696783L,746250567715L,746787438627L,747324309509L,747861180430L,748398051343L,748934922255L,749471793187L,750008664079L,750545535011L,751082405923L,751619276805L,752156147727L,752693018659L,753229889571L,753766760453L,754303631395L,754840502277L,755377373189L,755914244116L,756451115020L,756987985938L,757524856850L,758061727758L,758598598674L,759135469582L,759672340494L,760209211407L,760746082322L,761282953230L,761819824142L,762356695055L,762893565966L,763430436879L,763967307791L,764504178723L,765041049618L,765577920526L,766114791438L,766651662351L,767188533262L,767725404175L,768262275087L,768799146019L,769336016910L,769872887823L,770409758735L,770946629667L,771483500559L,772020371491L,772557242403L,773094113285L,773630984210L,774167855118L,774704726030L,775241596943L,775778467854L,776315338767L,776852209679L,777389080611L,777925951502L,778462822415L,778999693327L,779536564259L,780073435151L,780610306083L,781147176995L,781684047877L,782220918798L,782757789711L,783294660623L,783831531555L,784368402447L,784905273379L,785442144291L,785979015173L,786515886095L,787052757027L,787589627939L,788126498821L,788663369763L,789200240645L,789737111557L,790273982484L,790810853394L,791347724302L,791884595214L,792421466127L,792958337038L,793495207951L,794032078863L,794568949795L,795105820686L,795642691599L,796179562511L,796716433443L,797253304335L,797790175267L,798327046179L,798863917061L,799400787982L,799937658895L,800474529807L,801011400739L,801548271631L,802085142563L,802622013475L,803158884357L,803695755279L,804232626211L,804769497123L,805306368005L,805843238947L,806380109829L,806916980741L,807453851668L,807990722574L,808527593487L,809064464399L,809601335331L,810138206223L,810675077155L,811211948067L,811748818949L,812285689871L,812822560803L,813359431715L,813896302597L,814433173539L,814970044421L,815506915333L,816043786260L,816580657167L,817117528099L,817654399011L,818191269893L,818728140835L,819265011717L,819801882629L,820338753556L,820875624483L,821412495365L,821949366277L,822486237204L,823023108101L,823559979028L,824096849940L,824633720868L,825170591745L,825707462668L,826244333580L,826781204498L,827318075404L,827854946322L,828391817234L,828928688142L,829465559052L,830002429970L,830539300882L,831076171790L,831613042706L,832149913614L,832686784526L,833223655439L,833760526348L,834297397266L,834834268178L,835371139086L,835908010002L,836444880910L,836981751822L,837518622735L,838055493650L,838592364558L,839129235470L,839666106383L,840202977294L,840739848207L,841276719119L,841813590051L,842350460940L,842887331858L,843424202770L,843961073678L,844497944594L,845034815502L,845571686414L,846108557327L,846645428242L,847182299150L,847719170062L,848256040975L,848792911886L,849329782799L,849866653711L,850403524643L,850940395538L,851477266446L,852014137358L,852551008271L,853087879182L,853624750095L,854161621007L,854698491939L,855235362830L,855772233743L,856309104655L,856845975587L,857382846479L,857919717411L,858456588323L,858993459205L,859530330124L,860067201042L,860604071954L,861140942862L,861677813778L,862214684686L,862751555598L,863288426511L,863825297426L,864362168334L,864899039246L,865435910159L,865972781070L,866509651983L,867046522895L,867583393827L,868120264722L,868657135630L,869194006542L,869730877455L,870267748366L,870804619279L,871341490191L,871878361123L,872415232014L,872952102927L,873488973839L,874025844771L,874562715663L,875099586595L,875636457507L,876173328389L,876710199314L,877247070222L,877783941134L,878320812047L,878857682958L,879394553871L,879931424783L,880468295715L,881005166606L,881542037519L,882078908431L,882615779363L,883152650255L,883689521187L,884226392099L,884763262981L,885300133902L,885837004815L,886373875727L,886910746659L,887447617551L,887984488483L,888521359395L,889058230277L,889595101199L,890131972131L,890668843043L,891205713925L,891742584867L,892279455749L,892816326661L,893353197588L,893890068492L,894426939410L,894963810322L,895500681230L,896037552146L,896574423054L,897111293966L,897648164879L,898185035794L,898721906702L,899258777614L,899795648527L,900332519438L,900869390351L,901406261263L,901943132195L,902480003090L,903016873998L,903553744910L,904090615823L,904627486734L,905164357647L,905701228559L,906238099491L,906774970382L,907311841295L,907848712207L,908385583139L,908922454031L,909459324963L,909996195875L,910533066757L,911069937682L,911606808590L,912143679502L,912680550415L,913217421326L,913754292239L,914291163151L,914828034083L,915364904974L,915901775887L,916438646799L,916975517731L,917512388623L,918049259555L,918586130467L,919123001349L,919659872270L,920196743183L,920733614095L,921270485027L,921807355919L,922344226851L,922881097763L,923417968645L,923954839567L,924491710499L,925028581411L,925565452293L,926102323235L,926639194117L,927176065029L,927712935956L,928249806866L,928786677774L,929323548686L,929860419599L,930397290510L,930934161423L,931471032335L,932007903267L,932544774158L,933081645071L,933618515983L,934155386915L,934692257807L,935229128739L,935765999651L,936302870533L,936839741454L,937376612367L,937913483279L,938450354211L,938987225103L,939524096035L,940060966947L,940597837829L,941134708751L,941671579683L,942208450595L,942745321477L,943282192419L,943819063301L,944355934213L,944892805140L,945429676046L,945966546959L,946503417871L,947040288803L,947577159695L,948114030627L,948650901539L,949187772421L,949724643343L,950261514275L,950798385187L,951335256069L,951872127011L,952408997893L,952945868805L,953482739732L,954019610639L,954556481571L,955093352483L,955630223365L,956167094307L,956703965189L,957240836101L,957777707028L,958314577955L,958851448837L,959388319749L,959925190676L,960462061573L,960998932500L,961535803412L,962072674340L,962609545228L,963146416146L,963683287058L,964220157966L,964757028882L,965293899790L,965830770702L,966367641615L,966904512530L,967441383438L,967978254350L,968515125263L,969051996174L,969588867087L,970125737999L,970662608931L,971199479826L,971736350734L,972273221646L,972810092559L,973346963470L,973883834383L,974420705295L,974957576227L,975494447118L,976031318031L,976568188943L,977105059875L,977641930767L,978178801699L,978715672611L,979252543493L,979789414418L,980326285326L,980863156238L,981400027151L,981936898062L,982473768975L,983010639887L,983547510819L,984084381710L,984621252623L,985158123535L,985694994467L,986231865359L,986768736291L,987305607203L,987842478085L,988379349006L,988916219919L,989453090831L,989989961763L,990526832655L,991063703587L,991600574499L,992137445381L,992674316303L,993211187235L,993748058147L,994284929029L,994821799971L,995358670853L,995895541765L,996432412692L,996969283602L,997506154510L,998043025422L,998579896335L,999116767246L,999653638159L
};
long[] steps = {
0L,37921447L,73277740L,108634032L,141783308L,177139603L,210288879L,243438157L,274656312L,310012603L,343161879L,376311157L,407529312L,440678587L,471896742L,503114895L,532615214L,567971503L,601120779L,634270057L,665488212L,698637487L,729855642L,761073795L,790574114L,823723387L,854941542L,886159695L,915660014L,946878166L,976378485L,1005878803L,1033834916L,1069191206L,1102340482L,1135489760L,1166707915L,1199857190L,1231075345L,1262293498L,1291793817L,1324943090L,1356161245L,1387379398L,1416879717L,1448097869L,1477598188L,1507098506L,1535054619L,1568203893L,1599422048L,1630640201L,1660140520L,1691358672L,1720858991L,1750359309L,1778315422L,1809533574L,1839033893L,1868534211L,1896490324L,1925990643L,1953946756L,1981902869L,2008466475L,2043822765L,2076972041L,2110121319L,2141339474L,2174488749L,2205706904L,2236925057L,2266425376L,2299574649L,2330792804L,2362010957L,2391511276L,2422729428L,2452229747L,2481730065L,2509686178L,2542835452L,2574053607L,2605271760L,2634772079L,2665990231L,2695490550L,2724990868L,2752946981L,2784165133L,2813665452L,2843165770L,2871121883L,2900622202L,2928578315L,2956534428L,2983098034L,3016247307L,3047465462L,3078683615L,3108183934L,3139402086L,3168902405L,3198402723L,3226358836L,3257576988L,3287077307L,3316577625L,3344533738L,3374034057L,3401990170L,3429946283L,3456509889L,3487728041L,3517228360L,3546728678L,3574684791L,3604185110L,3632141223L,3660097336L,3686660942L,3716161260L,3744117373L,3772073486L,3798637092L,3826593205L,3853156811L,3879720417L,3905027107L,3940383392L,3973532668L,4006681946L,4037900101L,4071049376L,4102267531L,4133485684L,4162986003L,4196135276L,4227353431L,4258571584L,4288071903L,4319290055L,4348790374L,4378290692L,4406246805L,4439396079L,4470614234L,4501832387L,4531332706L,4562550858L,4592051177L,4621551495L,4649507608L,4680725760L,4710226079L,4739726397L,4767682510L,4797182829L,4825138942L,4853095055L,4879658661L,4912807934L,4944026089L,4975244242L,5004744561L,5035962713L,5065463032L,5094963350L,5122919463L,5154137615L,5183637934L,5213138252L,5241094365L,5270594684L,5298550797L,5326506910L,5353070516L,5384288668L,5413788987L,5443289305L,5471245418L,5500745737L,5528701850L,5556657963L,5583221569L,5612721887L,5640678000L,5668634113L,5695197719L,5723153832L,5749717438L,5776281044L,5801587734L,5834737004L,5865955159L,5897173312L,5926673631L,5957891783L,5987392102L,6016892420L,6044848533L,6076066685L,6105567004L,6135067322L,6163023435L,6192523754L,6220479867L,6248435980L,6274999586L,6306217738L,6335718057L,6365218375L,6393174488L,6422674807L,6450630920L,6478587033L,6505150639L,6534650957L,6562607070L,6590563183L,6617126789L,6645082902L,6671646508L,6698210114L,6723516804L,6754734952L,6784235271L,6813735589L,6841691702L,6871192021L,6899148134L,6927104247L,6953667853L,6983168171L,7011124284L,7039080397L,7065644003L,7093600116L,7120163722L,7146727328L,7172034018L,7201534334L,7229490447L,7257446560L,7284010166L,7311966279L,7338529885L,7365093491L,7390400181L,7418356291L,7444919897L,7471483503L,7496790193L,7523353797L,7548660487L,7573967175L,7598134125L,7633490419L,7666639695L,7699788973L,7731007128L,7764156403L,7795374558L,7826592711L,7856093030L,7889242303L,7920460458L,7951678611L,7981178930L,8012397082L,8041897401L,8071397719L,8099353832L,8132503106L,8163721261L,8194939414L,8224439733L,8255657885L,8285158204L,8314658522L,8342614635L,8373832787L,8403333106L,8432833424L,8460789537L,8490289856L,8518245969L,8546202082L,8572765688L,8605914961L,8637133116L,8668351269L,8697851588L,8729069740L,8758570059L,8788070377L,8816026490L,8847244642L,8876744961L,8906245279L,8934201392L,8963701711L,8991657824L,9019613937L,9046177543L,9077395695L,9106896014L,9136396332L,9164352445L,9193852764L,9221808877L,9249764990L,9276328596L,9305828914L,9333785027L,9361741140L,9388304746L,9416260859L,9442824465L,9469388071L,9494694761L,9527844031L,9559062186L,9590280339L,9619780658L,9650998810L,9680499129L,9709999447L,9737955560L,9769173712L,9798674031L,9828174349L,9856130462L,9885630781L,9913586894L,9941543007L,9968106613L,9999324765L,10028825084L,10058325402L,10086281515L,10115781834L,10143737947L,10171694060L,10198257666L,10227757984L,10255714097L,10283670210L,10310233816L,10338189929L,10364753535L,10391317141L,10416623831L,10447841979L,10477342298L,10506842616L,10534798729L,10564299048L,10592255161L,10620211274L,10646774880L,10676275198L,10704231311L,10732187424L,10758751030L,10786707143L,10813270749L,10839834355L,10865141045L,10894641361L,10922597474L,10950553587L,10977117193L,11005073306L,11031636912L,11058200518L,11083507208L,11111463318L,11138026924L,11164590530L,11189897220L,11216460824L,11241767514L,11267074202L,11291241152L,11324390428L,11355608583L,11386826736L,11416327055L,11447545207L,11477045526L,11506545844L,11534501957L,11565720109L,11595220428L,11624720746L,11652676859L,11682177178L,11710133291L,11738089404L,11764653010L,11795871162L,11825371481L,11854871799L,11882827912L,11912328231L,11940284344L,11968240457L,11994804063L,12024304381L,12052260494L,12080216607L,12106780213L,12134736326L,12161299932L,12187863538L,12213170228L,12244388376L,12273888695L,12303389013L,12331345126L,12360845445L,12388801558L,12416757671L,12443321277L,12472821595L,12500777708L,12528733821L,12555297427L,12583253540L,12609817146L,12636380752L,12661687442L,12691187758L,12719143871L,12747099984L,12773663590L,12801619703L,12828183309L,12854746915L,12880053605L,12908009715L,12934573321L,12961136927L,12986443617L,13013007221L,13038313911L,13063620599L,13087787549L,13119005703L,13148506022L,13178006340L,13205962453L,13235462772L,13263418885L,13291374998L,13317938604L,13347438922L,13375395035L,13403351148L,13429914754L,13457870867L,13484434473L,13510998079L,13536304769L,13565805085L,13593761198L,13621717311L,13648280917L,13676237030L,13702800636L,13729364242L,13754670932L,13782627042L,13809190648L,13835754254L,13861060944L,13887624548L,13912931238L,13938237926L,13962404876L,13991905196L,14019861309L,14047817422L,14074381028L,14102337141L,14128900747L,14155464353L,14180771043L,14208727153L,14235290759L,14261854365L,14287161055L,14313724659L,14339031349L,14364338037L,14388504987L,14416461101L,14443024707L,14469588313L,14494895003L,14521458607L,14546765297L,14572071985L,14596238935L,14622802542L,14648109232L,14673415920L,14697582870L,14722889561L,14747056511L,14771223463L,14794348661L,14829704950L,14862854226L,14896003504L,14927221659L,14960370934L,14991589089L,15022807242L,15052307561L,15085456834L,15116674989L,15147893142L,15177393461L,15208611613L,15238111932L,15267612250L,15295568363L,15328717637L,15359935792L,15391153945L,15420654264L,15451872416L,15481372735L,15510873053L,15538829166L,15570047318L,15599547637L,15629047955L,15657004068L,15686504387L,15714460500L,15742416613L,15768980219L,15802129492L,15833347647L,15864565800L,15894066119L,15925284271L,15954784590L,15984284908L,16012241021L,16043459173L,16072959492L,16102459810L,16130415923L,16159916242L,16187872355L,16215828468L,16242392074L,16273610226L,16303110545L,16332610863L,16360566976L,16390067295L,16418023408L,16445979521L,16472543127L,16502043445L,16529999558L,16557955671L,16584519277L,16612475390L,16639038996L,16665602602L,16690909292L,16724058562L,16755276717L,16786494870L,16815995189L,16847213341L,16876713660L,16906213978L,16934170091L,16965388243L,16994888562L,17024388880L,17052344993L,17081845312L,17109801425L,17137757538L,17164321144L,17195539296L,17225039615L,17254539933L,17282496046L,17311996365L,17339952478L,17367908591L,17394472197L,17423972515L,17451928628L,17479884741L,17506448347L,17534404460L,17560968066L,17587531672L,17612838362L,17644056510L,17673556829L,17703057147L,17731013260L,17760513579L,17788469692L,17816425805L,17842989411L,17872489729L,17900445842L,17928401955L,17954965561L,17982921674L,18009485280L,18036048886L,18061355576L,18090855892L,18118812005L,18146768118L,18173331724L,18201287837L,18227851443L,18254415049L,18279721739L,18307677849L,18334241455L,18360805061L,18386111751L,18412675355L,18437982045L,18463288733L,18487455683L,18520604959L,18551823114L,18583041267L,18612541586L,18643759738L,18673260057L,18702760375L,18730716488L,18761934640L,18791434959L,18820935277L,18848891390L,18878391709L,18906347822L,18934303935L,18960867541L,18992085693L,19021586012L,19051086330L,19079042443L,19108542762L,19136498875L,19164454988L,19191018594L,19220518912L,19248475025L,19276431138L,19302994744L,19330950857L,19357514463L,19384078069L,19409384759L,19440602907L,19470103226L,19499603544L,19527559657L,19557059976L,19585016089L,19612972202L,19639535808L,19669036126L,19696992239L,19724948352L,19751511958L,19779468071L,19806031677L,19832595283L,19857901973L,19887402289L,19915358402L,19943314515L,19969878121L,19997834234L,20024397840L,20050961446L,20076268136L,20104224246L,20130787852L,20157351458L,20182658148L,20209221752L,20234528442L,20259835130L,20284002080L,20315220234L,20344720553L,20374220871L,20402176984L,20431677303L,20459633416L,20487589529L,20514153135L,20543653453L,20571609566L,20599565679L,20626129285L,20654085398L,20680649004L,20707212610L,20732519300L,20762019616L,20789975729L,20817931842L,20844495448L,20872451561L,20899015167L,20925578773L,20950885463L,20978841573L,21005405179L,21031968785L,21057275475L,21083839079L,21109145769L,21134452457L,21158619407L,21188119727L,21216075840L,21244031953L,21270595559L,21298551672L,21325115278L,21351678884L,21376985574L,21404941684L,21431505290L,21458068896L,21483375586L,21509939190L,21535245880L,21560552568L,21584719518L,21612675632L,21639239238L,21665802844L,21691109534L,21717673138L,21742979828L,21768286516L,21792453466L,21819017073L,21844323763L,21869630451L,21893797401L,21919104092L,21943271042L,21967437994L,21990563192L,22023712465L,22054930620L,22086148773L,22115649092L,22146867244L,22176367563L,22205867881L,22233823994L,22265042146L,22294542465L,22324042783L,22351998896L,22381499215L,22409455328L,22437411441L,22463975047L,22495193199L,22524693518L,22554193836L,22582149949L,22611650268L,22639606381L,22667562494L,22694126100L,22723626418L,22751582531L,22779538644L,22806102250L,22834058363L,22860621969L,22887185575L,22912492265L,22943710413L,22973210732L,23002711050L,23030667163L,23060167482L,23088123595L,23116079708L,23142643314L,23172143632L,23200099745L,23228055858L,23254619464L,23282575577L,23309139183L,23335702789L,23361009479L,23390509795L,23418465908L,23446422021L,23472985627L,23500941740L,23527505346L,23554068952L,23579375642L,23607331752L,23633895358L,23660458964L,23685765654L,23712329258L,23737635948L,23762942636L,23787109586L,23818327740L,23847828059L,23877328377L,23905284490L,23934784809L,23962740922L,23990697035L,24017260641L,24046760959L,24074717072L,24102673185L,24129236791L,24157192904L,24183756510L,24210320116L,24235626806L,24265127122L,24293083235L,24321039348L,24347602954L,24375559067L,24402122673L,24428686279L,24453992969L,24481949079L,24508512685L,24535076291L,24560382981L,24586946585L,24612253275L,24637559963L,24661726913L,24691227233L,24719183346L,24747139459L,24773703065L,24801659178L,24828222784L,24854786390L,24880093080L,24908049190L,24934612796L,24961176402L,24986483092L,25013046696L,25038353386L,25063660074L,25087827024L,25115783138L,25142346744L,25168910350L,25194217040L,25220780644L,25246087334L,25271394022L,25295560972L,25322124579L,25347431269L,25372737957L,25396904907L,25422211598L,25446378548L,25470545500L,25493670698L,25524888849L,25554389168L,25583889486L,25611845599L,25641345918L,25669302031L,25697258144L,25723821750L,25753322068L,25781278181L,25809234294L,25835797900L,25863754013L,25890317619L,25916881225L,25942187915L,25971688231L,25999644344L,26027600457L,26054164063L,26082120176L,26108683782L,26135247388L,26160554078L,26188510188L,26215073794L,26241637400L,26266944090L,26293507694L,26318814384L,26344121072L,26368288022L,26397788342L,26425744455L,26453700568L,26480264174L,26508220287L,26534783893L,26561347499L,26586654189L,26614610299L,26641173905L,26667737511L,26693044201L,26719607805L,26744914495L,26770221183L,26794388133L,26822344247L,26848907853L,26875471459L,26900778149L,26927341753L,26952648443L,26977955131L,27002122081L,27028685688L,27053992378L,27079299066L,27103466016L,27128772707L,27152939657L,27177106609L,27200231807L,27229732125L,27257688238L,27285644351L,27312207957L,27340164070L,27366727676L,27393291282L,27418597972L,27446554082L,27473117688L,27499681294L,27524987984L,27551551588L,27576858278L,27602164966L,27626331916L,27654288030L,27680851636L,27707415242L,27732721932L,27759285536L,27784592226L,27809898914L,27834065864L,27860629471L,27885936161L,27911242849L,27935409799L,27960716490L,27984883440L,28009050392L,28032175590L,28060131702L,28086695308L,28113258914L,28138565604L,28165129208L,28190435898L,28215742586L,28239909536L,28266473143L,28291779833L,28317086521L,28341253471L,28366560162L,28390727112L,28414894064L,28438019262L,28464582869L,28489889559L,28515196247L,28539363197L,28564669888L,28588836838L,28613003790L,28636128988L,28661435677L,28685602627L,28709769579L,28732894777L,28757061728L,28780186926L,28803312122L,28825478386L,28860834671L,28893983947L,28927133225L,28958351380L,28991500655L,29022718810L,29053936963L,29083437282L,29116586555L,29147804710L,29179022863L,29208523182L,29239741334L,29269241653L,29298741971L,29326698084L,29359847358L,29391065513L,29422283666L,29451783985L,29483002137L,29512502456L,29542002774L,29569958887L,29601177039L,29630677358L,29660177676L,29688133789L,29717634108L,29745590221L,29773546334L,29800109940L,29833259213L,29864477368L,29895695521L,29925195840L,29956413992L,29985914311L,30015414629L,30043370742L,30074588894L,30104089213L,30133589531L,30161545644L,30191045963L,30219002076L,30246958189L,30273521795L,30304739947L,30334240266L,30363740584L,30391696697L,30421197016L,30449153129L,30477109242L,30503672848L,30533173166L,30561129279L,30589085392L,30615648998L,30643605111L,30670168717L,30696732323L,30722039013L,30755188283L,30786406438L,30817624591L,30847124910L,30878343062L,30907843381L,30937343699L,30965299812L,30996517964L,31026018283L,31055518601L,31083474714L,31112975033L,31140931146L,31168887259L,31195450865L,31226669017L,31256169336L,31285669654L,31313625767L,31343126086L,31371082199L,31399038312L,31425601918L,31455102236L,31483058349L,31511014462L,31537578068L,31565534181L,31592097787L,31618661393L,31643968083L,31675186231L,31704686550L,31734186868L,31762142981L,31791643300L,31819599413L,31847555526L,31874119132L,31903619450L,31931575563L,31959531676L,31986095282L,32014051395L,32040615001L,32067178607L,32092485297L,32121985613L,32149941726L,32177897839L,32204461445L,32232417558L,32258981164L,32285544770L,32310851460L,32338807570L,32365371176L,32391934782L,32417241472L,32443805076L,32469111766L,32494418454L,32518585404L,32551734680L,32582952835L,32614170988L,32643671307L,32674889459L,32704389778L,32733890096L,32761846209L,32793064361L,32822564680L,32852064998L,32880021111L,32909521430L,32937477543L,32965433656L,32991997262L,33023215414L,33052715733L,33082216051L,33110172164L,33139672483L,33167628596L,33195584709L,33222148315L,33251648633L,33279604746L,33307560859L,33334124465L,33362080578L,33388644184L,33415207790L,33440514480L,33471732628L,33501232947L,33530733265L,33558689378L,33588189697L,33616145810L,33644101923L,33670665529L,33700165847L,33728121960L,33756078073L,33782641679L,33810597792L,33837161398L,33863725004L,33889031694L,33918532010L,33946488123L,33974444236L,34001007842L,34028963955L,34055527561L,34082091167L,34107397857L,34135353967L,34161917573L,34188481179L,34213787869L,34240351473L,34265658163L,34290964851L,34315131801L,34346349955L,34375850274L,34405350592L,34433306705L,34462807024L,34490763137L,34518719250L,34545282856L,34574783174L,34602739287L,34630695400L,34657259006L,34685215119L,34711778725L,34738342331L,34763649021L,34793149337L,34821105450L,34849061563L,34875625169L,34903581282L,34930144888L,34956708494L,34982015184L,35009971294L,35036534900L,35063098506L,35088405196L,35114968800L,35140275490L,35165582178L,35189749128L,35219249448L,35247205561L,35275161674L,35301725280L,35329681393L,35356244999L,35382808605L,35408115295L,35436071405L,35462635011L,35489198617L,35514505307L,35541068911L,35566375601L,35591682289L,35615849239L,35643805353L,35670368959L,35696932565L,35722239255L,35748802859L,35774109549L,35799416237L,35823583187L,35850146794L,35875453484L,35900760172L,35924927122L,35950233813L,35974400763L,35998567715L,36021692913L,36054842186L,36086060341L,36117278494L,36146778813L,36177996965L,36207497284L,36236997602L,36264953715L,36296171867L,36325672186L,36355172504L,36383128617L,36412628936L,36440585049L,36468541162L,36495104768L,36526322920L,36555823239L,36585323557L,36613279670L,36642779989L,36670736102L,36698692215L,36725255821L,36754756139L,36782712252L,36810668365L,36837231971L,36865188084L,36891751690L,36918315296L,36943621986L,36974840134L,37004340453L,37033840771L,37061796884L,37091297203L,37119253316L,37147209429L,37173773035L,37203273353L,37231229466L,37259185579L,37285749185L,37313705298L,37340268904L,37366832510L,37392139200L,37421639516L,37449595629L,37477551742L,37504115348L,37532071461L,37558635067L,37585198673L,37610505363L,37638461473L,37665025079L,37691588685L,37716895375L,37743458979L,37768765669L,37794072357L,37818239307L,37849457461L,37878957780L,37908458098L,37936414211L,37965914530L,37993870643L,38021826756L,38048390362L,38077890680L,38105846793L,38133802906L,38160366512L,38188322625L,38214886231L,38241449837L,38266756527L,38296256843L,38324212956L,38352169069L,38378732675L,38406688788L,38433252394L,38459816000L,38485122690L,38513078800L,38539642406L,38566206012L,38591512702L,38618076306L,38643382996L,38668689684L,38692856634L,38722356954L,38750313067L,38778269180L,38804832786L,38832788899L,38859352505L,38885916111L,38911222801L,38939178911L,38965742517L,38992306123L,39017612813L,39044176417L,39069483107L,39094789795L,39118956745L,39146912859L,39173476465L,39200040071L,39225346761L,39251910365L,39277217055L,39302523743L,39326690693L,39353254300L,39378560990L,39403867678L,39428034628L,39453341319L,39477508269L,39501675221L,39524800419L,39556018570L,39585518889L,39615019207L,39642975320L,39672475639L,39700431752L,39728387865L,39754951471L,39784451789L,39812407902L,39840364015L,39866927621L,39894883734L,39921447340L,39948010946L,39973317636L,40002817952L,40030774065L,40058730178L,40085293784L,40113249897L,40139813503L,40166377109L,40191683799L,40219639909L,40246203515L,40272767121L,40298073811L,40324637415L,40349944105L,40375250793L,40399417743L,40428918063L,40456874176L,40484830289L,40511393895L,40539350008L,40565913614L,40592477220L,40617783910L,40645740020L,40672303626L,40698867232L,40724173922L,40750737526L,40776044216L,40801350904L,40825517854L,40853473968L,40880037574L,40906601180L,40931907870L,40958471474L,40983778164L,41009084852L,41033251802L,41059815409L,41085122099L,41110428787L,41134595737L,41159902428L,41184069378L,41208236330L,41231361528L,41260861846L,41288817959L,41316774072L,41343337678L,41371293791L,41397857397L,41424421003L,41449727693L,41477683803L,41504247409L,41530811015L,41556117705L,41582681309L,41607987999L,41633294687L,41657461637L,41685417751L,41711981357L,41738544963L,41763851653L,41790415257L,41815721947L,41841028635L,41865195585L,41891759192L,41917065882L,41942372570L,41966539520L,41991846211L,42016013161L,42040180113L,42063305311L,42091261423L,42117825029L,42144388635L,42169695325L,42196258929L,42221565619L,42246872307L,42271039257L,42297602864L,42322909554L,42348216242L,42372383192L,42397689883L,42421856833L,42446023785L,42469148983L,42495712590L,42521019280L,42546325968L,42570492918L,42595799609L,42619966559L,42644133511L,42667258709L,42692565398L,42716732348L,42740899300L,42764024498L,42788191449L,42811316647L,42834441843L,42856608107L,42889757377L,42920975532L,42952193685L,42981694004L,43012912156L,43042412475L,43071912793L,43099868906L,43131087058L,43160587377L,43190087695L,43218043808L,43247544127L,43275500240L,43303456353L,43330019959L,43361238111L,43390738430L,43420238748L,43448194861L,43477695180L,43505651293L,43533607406L,43560171012L,43589671330L,43617627443L,43645583556L,43672147162L,43700103275L,43726666881L,43753230487L,43778537177L,43809755325L,43839255644L,43868755962L,43896712075L,43926212394L,43954168507L,43982124620L,44008688226L,44038188544L,44066144657L,44094100770L,44120664376L,44148620489L,44175184095L,44201747701L,44227054391L,44256554707L,44284510820L,44312466933L,44339030539L,44366986652L,44393550258L,44420113864L,44445420554L,44473376664L,44499940270L,44526503876L,44551810566L,44578374170L,44603680860L,44628987548L,44653154498L,44684372652L,44713872971L,44743373289L,44771329402L,44800829721L,44828785834L,44856741947L,44883305553L,44912805871L,44940761984L,44968718097L,44995281703L,45023237816L,45049801422L,45076365028L,45101671718L,45131172034L,45159128147L,45187084260L,45213647866L,45241603979L,45268167585L,45294731191L,45320037881L,45347993991L,45374557597L,45401121203L,45426427893L,45452991497L,45478298187L,45503604875L,45527771825L,45557272145L,45585228258L,45613184371L,45639747977L,45667704090L,45694267696L,45720831302L,45746137992L,45774094102L,45800657708L,45827221314L,45852528004L,45879091608L,45904398298L,45929704986L,45953871936L,45981828050L,46008391656L,46034955262L,46060261952L,46086825556L,46112132246L,46137438934L,46161605884L,46188169491L,46213476181L,46238782869L,46262949819L,46288256510L,46312423460L,46336590412L,46359715610L,46390933761L,46420434080L,46449934398L,46477890511L,46507390830L,46535346943L,46563303056L,46589866662L,46619366980L,46647323093L,46675279206L,46701842812L,46729798925L,46756362531L,46782926137L,46808232827L,46837733143L,46865689256L,46893645369L,46920208975L,46948165088L,46974728694L,47001292300L,47026598990L,47054555100L,47081118706L,47107682312L,47132989002L,47159552606L,47184859296L,47210165984L,47234332934L,47263833254L,47291789367L,47319745480L,47346309086L,47374265199L,47400828805L,47427392411L,47452699101L,47480655211L,47507218817L,47533782423L,47559089113L,47585652717L,47610959407L,47636266095L,47660433045L,47688389159L,47714952765L,47741516371L,47766823061L,47793386665L,47818693355L,47844000043L,47868166993L,47894730600L,47920037290L,47945343978L,47969510928L,47994817619L,48018984569L,48043151521L,48066276719L,48095777037L,48123733150L,48151689263L,48178252869L,48206208982L,48232772588L,48259336194L,48284642884L,48312598994L,48339162600L,48365726206L,48391032896L,48417596500L,48442903190L,48468209878L,48492376828L,48520332942L,48546896548L,48573460154L,48598766844L,48625330448L,48650637138L,48675943826L,48700110776L,48726674383L,48751981073L,48777287761L,48801454711L,48826761402L,48850928352L,48875095304L,48898220502L,48926176614L,48952740220L,48979303826L,49004610516L,49031174120L,49056480810L,49081787498L,49105954448L,49132518055L,49157824745L,49183131433L,49207298383L,49232605074L,49256772024L,49280938976L,49304064174L,49330627781L,49355934471L,49381241159L,49405408109L,49430714800L,49454881750L,49479048702L,49502173900L,49527480589L,49551647539L,49575814491L,49598939689L,49623106640L,49646231838L,49669357034L,49691523298L,49722741446L,49752241765L,49781742083L,49809698196L,49839198515L,49867154628L,49895110741L,49921674347L,49951174665L,49979130778L,50007086891L,50033650497L,50061606610L,50088170216L,50114733822L,50140040512L,50169540828L,50197496941L,50225453054L,50252016660L,50279972773L,50306536379L,50333099985L,50358406675L,50386362785L,50412926391L,50439489997L,50464796687L,50491360291L,50516666981L,50541973669L,50566140619L,50595640939L,50623597052L,50651553165L,50678116771L,50706072884L,50732636490L,50759200096L,50784506786L,50812462896L,50839026502L,50865590108L,50890896798L,50917460402L,50942767092L,50968073780L,50992240730L,51020196844L,51046760450L,51073324056L,51098630746L,51125194350L,51150501040L,51175807728L,51199974678L,51226538285L,51251844975L,51277151663L,51301318613L,51326625304L,51350792254L,51374959206L,51398084404L,51427584722L,51455540835L,51483496948L,51510060554L,51538016667L,51564580273L
};
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Q402B().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}