1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 18 18 20 19 22 20 24 21 26 22 28 23 30 24 33 25 36 26 40 27 44 28 48 29 52 30 56 31 60 32 66 33 72 34 80 35 88 36 96 37 104 38 112 39 120 40 132 41 144 42 160 43 176 44 192 45 208 46 224 47 240 48 264 49 288 50 320 51 352 52 384 53 416 54 448 55 480 56 528 57 576 58 640 59 704 60 768 61 832 62 896 63 960 64 1056 65 1152 66 1280 67 1408 68 1536 69 1664 70 1792 71 1920 72 2112 73 2304 74 2560 75 2816 76 3072 77 3328 78 3584 79 3840 80 4224 81 4608 82 5120 83 5632 84 6144 85 6656 86 7168 87 7680 88 8448 89 9216 90 10240 91 11264 92 12288 93 13312 94 14336 95 15360 96 16896 97 18432 98 20480 99 22528 100 24576 101 26624 102 28672 103 30720 104 33792 105 36864 106 40960 107 45056 108 49152 109 53248 110 57344 111 61440 112 67584 113 73728 114 81920 115 90112 116 98304 117 106496 118 114688 119 122880 120 135168 121 147456 122 163840 123 180224 124 196608 125 212992 126 229376 127 245760 128 270336 129 294912 130 327680 131 360448 132 393216 133 425984 134 458752 135 491520 136 540672 137 589824 138 655360 139 720896 140 786432 141 851968 142 917504 143 983040 144 1081344 145 1179648 146 1310720 147 1441792 148 1572864 149 1703936 150 1835008 151 1966080 152 2162688 153 2359296 154 2621440 155 2883584 156 3145728 157 3407872 158 3670016 159 3932160 160 4325376 161 4718592 162 5242880 163 5767168 164 6291456 165 6815744 166 7340032 167 7864320 168 8650752 169 9437184 170 10485760 171 11534336 172 12582912 173 13631488 174 14680064 175 15728640 176 17301504 177 18874368 178 20971520 179 23068672 180 25165824 181 27262976 182 29360128 183 31457280 184 34603008 185 37748736 186 41943040 187 46137344 188 50331648 189 54525952 190 58720256 191 62914560 192 69206016 193 75497472 194 83886080 195 92274688 196 100663296 197 109051904 198 117440512 199 125829120 200 138412032 201 150994944 202 167772160 203 184549376 204 201326592 205 218103808 206 234881024 207 251658240 208 276824064 209 301989888 210 335544320 211 369098752 212 402653184 213 436207616 214 469762048 215 503316480 216 553648128 217 603979776 218 671088640 219 738197504 220 805306368 221 872415232 222 939524096 223 1006632960 224 1107296256 225 1207959552 226 1342177280 227 1476395008 228 1610612736 229 1744830464 230 1879048192 231 2013265920 232 2214592512 233 2415919104 234 2684354560 235 2952790016 236 3221225472 237 3489660928 238 3758096384 239 4026531840 240 4429185024 241 4831838208 242 5368709120 243 5905580032 244 6442450944 245 6979321856 246 7516192768 247 8053063680 248 8858370048 249 9663676416 250 10737418240 251 11811160064 252 12884901888 253 13958643712 254 15032385536 255 16106127360 256 17716740096 257 19327352832 258 21474836480 259 23622320128 260 25769803776 261 27917287424 262 30064771072 263 32212254720 264 35433480192 265 38654705664 266 42949672960 267 47244640256 268 51539607552 269 55834574848 270 60129542144 271 64424509440 272 70866960384 273 77309411328 274 85899345920 275 94489280512 276 103079215104 277 111669149696 278 120259084288 279 128849018880 280 141733920768 281 154618822656 282 171798691840 283 188978561024 284 206158430208 285 223338299392 286 240518168576 287 257698037760 288 283467841536 289 309237645312 290 343597383680 291 377957122048 292 412316860416 293 446676598784 294 481036337152 295 515396075520 296 566935683072 297 618475290624 298 687194767360 299 755914244096 300 824633720832 301 893353197568 302 962072674304 303 1030792151040 304 1133871366144 305 1236950581248 306 1374389534720 307 1511828488192 308 1649267441664 309 1786706395136 310 1924145348608 311 2061584302080 312 2267742732288 313 2473901162496 314 2748779069440 315 3023656976384 316 3298534883328 317 3573412790272 318 3848290697216 319 4123168604160 320 4535485464576 321 4947802324992 322 5497558138880 323 6047313952768 324 6597069766656 325 7146825580544 326 7696581394432 327 8246337208320 328 9070970929152 329 9895604649984 330 10995116277760 331 12094627905536 332 13194139533312 333 14293651161088 334 15393162788864 335 16492674416640 336 18141941858304 337 19791209299968 338 21990232555520 339 24189255811072 340 26388279066624 341 28587302322176 342 30786325577728 343 32985348833280 344 36283883716608 345 39582418599936 346 43980465111040 347 48378511622144 348 52776558133248 349 57174604644352 350 61572651155456 351 65970697666560 352 72567767433216 353 79164837199872 354 87960930222080 355 96757023244288 356 105553116266496 357 114349209288704 358 123145302310912 359 131941395333120 360 145135534866432 361 158329674399744 362 175921860444160 363 193514046488576 364 211106232532992 365 228698418577408 366 246290604621824 367 263882790666240 368 290271069732864 369 316659348799488 370 351843720888320 371 387028092977152 372 422212465065984 373 457396837154816 374 492581209243648 375 527765581332480 376 580542139465728 377 633318697598976 378 703687441776640 379 774056185954304 380 844424930131968 381 914793674309632 382 985162418487296 383 1055531162664960 384 1161084278931456 385 1266637395197952 386 1407374883553280 387 1548112371908608 388 1688849860263936 389 1829587348619264 390 1970324836974592 391 2111062325329920 392 2322168557862912 393 2533274790395904 394 2814749767106560 395 3096224743817216 396 3377699720527872 397 3659174697238528 398 3940649673949184 399 4222124650659840 400 4644337115725824 401 5066549580791808 402 5629499534213120 403 6192449487634432 404 6755399441055744 405 7318349394477056 406 7881299347898368 407 8444249301319680 408 9288674231451648 409 10133099161583616 410 11258999068426240 411 12384898975268864 412 13510798882111488 413 14636698788954112 414 15762598695796736 415 16888498602639360 416 18577348462903296 417 20266198323167232 418 22517998136852480 419 24769797950537728 420 27021597764222976 421 29273397577908224 422 31525197391593472 423 33776997205278720 424 37154696925806592 425 40532396646334464 426 45035996273704960 427 49539595901075456 428 54043195528445952 429 58546795155816448 430 63050394783186944 431 67553994410557440 432 74309393851613184 433 81064793292668928 434 90071992547409920 435 99079191802150912 436 108086391056891904 437 117093590311632896 438 126100789566373888 439 135107988821114880 440 148618787703226368 441 162129586585337856 442 180143985094819840 443 198158383604301824 444 216172782113783808 445 234187180623265792 446 252201579132747776 447 270215977642229760 448 297237575406452736 449 324259173170675712 450 360287970189639680 451 396316767208603648 452 432345564227567616 453 468374361246531584 454 504403158265495552 455 540431955284459520 456 594475150812905472 457 648518346341351424 458 720575940379279360 459 792633534417207296 460 864691128455135232 461 936748722493063168 462 1008806316530991104 463 1080863910568919040 464 1188950301625810944 465 1297036692682702848 466 1441151880758558720 467 1585267068834414592 468 1729382256910270464 469 1873497444986126336 470 2017612633061982208 471 2161727821137838080 472 2377900603251621888 473 2594073385365405696 474 2882303761517117440 475 3170534137668829184 476 3458764513820540928 477 3746994889972252672 478 4035225266123964416 479 4323455642275676160 480 4755801206503243776 481 5188146770730811392 482 5764607523034234880 483 6341068275337658368 484 6917529027641081856 485 7493989779944505344 486 8070450532247928832 487 8646911284551352320 488 9511602413006487552 489 10376293541461622784 490 11529215046068469760 491 12682136550675316736 492 13835058055282163712 493 14987979559889010688 494 16140901064495857664 495 17293822569102704640 496 19023204826012975104 497 20752587082923245568 498 23058430092136939520 499 25364273101350633472 500 27670116110564327424 501 29975959119778021376 502 32281802128991715328 503 34587645138205409280 504 38046409652025950208 505 41505174165846491136 506 46116860184273879040 507 50728546202701266944 508 55340232221128654848 509 59951918239556042752 510 64563604257983430656 511 69175290276410818560 512 76092819304051900416 513 83010348331692982272 514 92233720368547758080 515 101457092405402533888 516 110680464442257309696 517 119903836479112085504 518 129127208515966861312 519 138350580552821637120 520 152185638608103800832 521 166020696663385964544 522 184467440737095516160 523 202914184810805067776 524 221360928884514619392 525 239807672958224171008 526 258254417031933722624 527 276701161105643274240 528 304371277216207601664 529 332041393326771929088 530 368934881474191032320 531 405828369621610135552 532 442721857769029238784 533 479615345916448342016 534 516508834063867445248 535 553402322211286548480 536 608742554432415203328 537 664082786653543858176 538 737869762948382064640 539 811656739243220271104 540 885443715538058477568 541 959230691832896684032 542 1033017668127734890496 543 1106804644422573096960 544 1217485108864830406656 545 1328165573307087716352 546 1475739525896764129280 547 1623313478486440542208 548 1770887431076116955136 549 1918461383665793368064 550 2066035336255469780992 551 2213609288845146193920 552 2434970217729660813312 553 2656331146614175432704 554 2951479051793528258560 555 3246626956972881084416 556 3541774862152233910272 557 3836922767331586736128 558 4132070672510939561984 559 4427218577690292387840 560 4869940435459321626624 561 5312662293228350865408 562 5902958103587056517120 563 6493253913945762168832 564 7083549724304467820544 565 7673845534663173472256 566 8264141345021879123968 567 8854437155380584775680 568 9739880870918643253248 569 10625324586456701730816 570 11805916207174113034240 571 12986507827891524337664 572 14167099448608935641088 573 15347691069326346944512 574 16528282690043758247936 575 17708874310761169551360 576 19479761741837286506496 577 21250649172913403461632 578 23611832414348226068480 579 25973015655783048675328 580 28334198897217871282176 581 30695382138652693889024 582 33056565380087516495872 583 35417748621522339102720 584 38959523483674573012992 585 42501298345826806923264 586 47223664828696452136960 587 51946031311566097350656 588 56668397794435742564352 589 61390764277305387778048 590 66113130760175032991744 591 70835497243044678205440 592 77919046967349146025984 593 85002596691653613846528 594 94447329657392904273920 595 103892062623132194701312 596 113336795588871485128704 597 122781528554610775556096 598 132226261520350065983488 599 141670994486089356410880 600 155838093934698292051968 601 170005193383307227693056 602 188894659314785808547840 603 207784125246264389402624 604 226673591177742970257408 605 245563057109221551112192 606 264452523040700131966976 607 283341988972178712821760 608 311676187869396584103936 609 340010386766614455386112 610 377789318629571617095680 611 415568250492528778805248 612 453347182355485940514816 613 491126114218443102224384 614 528905046081400263933952 615 566683977944357425643520 616 623352375738793168207872 617 680020773533228910772224 618 755578637259143234191360 619 831136500985057557610496 620 906694364710971881029632 621 982252228436886204448768 622 1057810092162800527867904 623 1133367955888714851287040 624 1246704751477586336415744 625 1360041547066457821544448 626 1511157274518286468382720 627 1662273001970115115220992 628 1813388729421943762059264 629 1964504456873772408897536 630 2115620184325601055735808 631 2266735911777429702574080 632 2493409502955172672831488 633 2720083094132915643088896 634 3022314549036572936765440 635 3324546003940230230441984 636 3626777458843887524118528 637 3929008913747544817795072 638 4231240368651202111471616 639 4533471823554859405148160 640 4986819005910345345662976 641 5440166188265831286177792 642 6044629098073145873530880 643 6649092007880460460883968 644 7253554917687775048237056 645 7858017827495089635590144 646 8462480737302404222943232 647 9066943647109718810296320 648 9973638011820690691325952 649 10880332376531662572355584 650 12089258196146291747061760 651 13298184015760920921767936 652 14507109835375550096474112 653 15716035654990179271180288 654 16924961474604808445886464 655 18133887294219437620592640 656 19947276023641381382651904 657 21760664753063325144711168 658 24178516392292583494123520 659 26596368031521841843535872 660 29014219670751100192948224 661 31432071309980358542360576 662 33849922949209616891772928 663 36267774588438875241185280 664 39894552047282762765303808 665 43521329506126650289422336 666 48357032784585166988247040 667 53192736063043683687071744 668 58028439341502200385896448 669 62864142619960717084721152 670 67699845898419233783545856 671 72535549176877750482370560 672 79789104094565525530607616 673 87042659012253300578844672 674 96714065569170333976494080 675 106385472126087367374143488 676 116056878683004400771792896 677 125728285239921434169442304 678 135399691796838467567091712 679 145071098353755500964741120 680 159578208189131051061215232 681 174085318024506601157689344 682 193428131138340667952988160 683 212770944252174734748286976 684 232113757366008801543585792 685 251456570479842868338884608 686 270799383593676935134183424 687 290142196707511001929482240 688 319156416378262102122430464 689 348170636049013202315378688 690 386856262276681335905976320 691 425541888504349469496573952 692 464227514732017603087171584 693 502913140959685736677769216 694 541598767187353870268366848 695 580284393415022003858964480 696 638312832756524204244860928 697 696341272098026404630757376 698 773712524553362671811952640 699 851083777008698938993147904 700 928455029464035206174343168 701 1005826281919371473355538432 702 1083197534374707740536733696 703 1160568786830044007717928960 704 1276625665513048408489721856 705 1392682544196052809261514752 706 1547425049106725343623905280 707 1702167554017397877986295808 708 1856910058928070412348686336 709 2011652563838742946711076864 710 2166395068749415481073467392 711 2321137573660088015435857920 712 2553251331026096816979443712 713 2785365088392105618523029504 714 3094850098213450687247810560 715 3404335108034795755972591616 716 3713820117856140824697372672 717 4023305127677485893422153728 718 4332790137498830962146934784 719 4642275147320176030871715840 720 5106502662052193633958887424 721 5570730176784211237046059008 722 6189700196426901374495621120 723 6808670216069591511945183232 724 7427640235712281649394745344 725 8046610255354971786844307456 726 8665580274997661924293869568 727 9284550294640352061743431680 728 10213005324104387267917774848 729 11141460353568422474092118016 730 12379400392853802748991242240 731 13617340432139183023890366464 732 14855280471424563298789490688 733 16093220510709943573688614912 734 17331160549995323848587739136 735 18569100589280704123486863360 736 20426010648208774535835549696 737 22282920707136844948184236032 738 24758800785707605497982484480 739 27234680864278366047780732928 740 29710560942849126597578981376 741 32186441021419887147377229824 742 34662321099990647697175478272 743 37138201178561408246973726720 744 40852021296417549071671099392 745 44565841414273689896368472064 746 49517601571415210995964968960 747 54469361728556732095561465856 748 59421121885698253195157962752 749 64372882042839774294754459648 750 69324642199981295394350956544 751 74276402357122816493947453440 752 81704042592835098143342198784 753 89131682828547379792736944128 754 99035203142830421991929937920 755 108938723457113464191122931712 756 118842243771396506390315925504 757 128745764085679548589508919296 758 138649284399962590788701913088 759 148552804714245632987894906880 760 163408085185670196286684397568 761 178263365657094759585473888256 762 198070406285660843983859875840 763 217877446914226928382245863424 764 237684487542793012780631851008 765 257491528171359097179017838592 766 277298568799925181577403826176 767 297105609428491265975789813760 768 326816170371340392573368795136 769 356526731314189519170947776512 770 396140812571321687967719751680 771 435754893828453856764491726848 772 475368975085586025561263702016 773 514983056342718194358035677184 774 554597137599850363154807652352 775 594211218856982531951579627520 776 653632340742680785146737590272 777 713053462628379038341895553024 778 792281625142643375935439503360 779 871509787656907713528983453696 780 950737950171172051122527404032 781 1029966112685436388716071354368 782 1109194275199700726309615304704 783 1188422437713965063903159255040 784 1307264681485361570293475180544 785 1426106925256758076683791106048 786 1584563250285286751870879006720 787 1743019575313815427057966907392 788 1901475900342344102245054808064 789 2059932225370872777432142708736 790 2218388550399401452619230609408 791 2376844875427930127806318510080 792 2614529362970723140586950361088 793 2852213850513516153367582212096 794 3169126500570573503741758013440 795 3486039150627630854115933814784 796 3802951800684688204490109616128 797 4119864450741745554864285417472 798 4436777100798802905238461218816 799 4753689750855860255612637020160 800 5229058725941446281173900722176 801 5704427701027032306735164424192 802 6338253001141147007483516026880 803 6972078301255261708231867629568 804 7605903601369376408980219232256 805 8239728901483491109728570834944 806 8873554201597605810476922437632 807 9507379501711720511225274040320 808 10458117451882892562347801444352 809 11408855402054064613470328848384 810 12676506002282294014967032053760 811 13944156602510523416463735259136 812 15211807202738752817960438464512 813 16479457802966982219457141669888 814 17747108403195211620953844875264 815 19014759003423441022450548080640 816 20916234903765785124695602888704 817 22817710804108129226940657696768 818 25353012004564588029934064107520 819 27888313205021046832927470518272 820 30423614405477505635920876929024 821 32958915605933964438914283339776 822 35494216806390423241907689750528 823 38029518006846882044901096161280 824 41832469807531570249391205777408 825 45635421608216258453881315393536 826 50706024009129176059868128215040 827 55776626410042093665854941036544 828 60847228810955011271841753858048 829 65917831211867928877828566679552 830 70988433612780846483815379501056 831 76059036013693764089802192322560 832 83664939615063140498782411554816 833 91270843216432516907762630787072 834 101412048018258352119736256430080 835 111553252820084187331709882073088 836 121694457621910022543683507716096 837 131835662423735857755657133359104 838 141976867225561692967630759002112 839 152118072027387528179604384645120 840 167329879230126280997564823109632 841 182541686432865033815525261574144 842 202824096036516704239472512860160 843 223106505640168374663419764146176 844 243388915243820045087367015432192 845 263671324847471715511314266718208 846 283953734451123385935261518004224 847 304236144054775056359208769290240 848 334659758460252561995129646219264 849 365083372865730067631050523148288 850 405648192073033408478945025720320 851 446213011280336749326839528292352 852 486777830487640090174734030864384 853 527342649694943431022628533436416 854 567907468902246771870523036008448 855 608472288109550112718417538580480 856 669319516920505123990259292438528 857 730166745731460135262101046296576 858 811296384146066816957890051440640 859 892426022560673498653679056584704 860 973555660975280180349468061728768 861 1054685299389886862045257066872832 862 1135814937804493543741046072016896 863 1216944576219100225436835077160960 864 1338639033841010247980518584877056 865 1460333491462920270524202092593152 866 1622592768292133633915780102881280 867 1784852045121346997307358113169408 868 1947111321950560360698936123457536 869 2109370598779773724090514133745664 870 2271629875608987087482092144033792 871 2433889152438200450873670154321920 872 2677278067682020495961037169754112 873 2920666982925840541048404185186304 874 3245185536584267267831560205762560 875 3569704090242693994614716226338816 876 3894222643901120721397872246915072 877 4218741197559547448181028267491328 878 4543259751217974174964184288067584 879 4867778304876400901747340308643840 880 5354556135364040991922074339508224 881 5841333965851681082096808370372608 882 6490371073168534535663120411525120 883 7139408180485387989229432452677632 884 7788445287802241442795744493830144 885 8437482395119094896362056534982656 886 9086519502435948349928368576135168 887 9735556609752801803494680617287680 888 10709112270728081983844148679016448 889 11682667931703362164193616740745216 890 12980742146337069071326240823050240 891 14278816360970775978458864905355264 892 15576890575604482885591488987660288 893 16874964790238189792724113069965312 894 18173039004871896699856737152270336 895 19471113219505603606989361234575360 896 21418224541456163967688297358032896 897 23365335863406724328387233481490432 898 25961484292674138142652481646100480 899 28557632721941551956917729810710528 900 31153781151208965771182977975320576 901 33749929580476379585448226139930624 902 36346078009743793399713474304540672 903 38942226439011207213978722469150720 904 42836449082912327935376594716065792 905 46730671726813448656774466962980864 906 51922968585348276285304963292200960 907 57115265443883103913835459621421056 908 62307562302417931542365955950641152 909 67499859160952759170896452279861248 910 72692156019487586799426948609081344 911 77884452878022414427957444938301440 912 85672898165824655870753189432131584 913 93461343453626897313548933925961728 914 103845937170696552570609926584401920 915 114230530887766207827670919242842112 916 124615124604835863084731911901282304 917 134999718321905518341792904559722496 918 145384312038975173598853897218162688 919 155768905756044828855914889876602880 920 171345796331649311741506378864263168 921 186922686907253794627097867851923456 922 207691874341393105141219853168803840 923 228461061775532415655341838485684224 924 249230249209671726169463823802564608 925 269999436643811036683585809119444992 926 290768624077950347197707794436325376 927 311537811512089657711829779753205760 928 342691592663298623483012757728526336 929 373845373814507589254195735703846912 930 415383748682786210282439706337607680 931 456922123551064831310683676971368448 932 498460498419343452338927647605129216 933 539998873287622073367171618238889984 934 581537248155900694395415588872650752 935 623075623024179315423659559506411520 936 685383185326597246966025515457052672 937 747690747629015178508391471407693824 938 830767497365572420564879412675215360 939 913844247102129662621367353942736896 940 996920996838686904677855295210258432 941 1079997746575244146734343236477779968 942 1163074496311801388790831177745301504 943 1246151246048358630847319119012823040 944 1370766370653194493932051030914105344 945 1495381495258030357016782942815387648 946 1661534994731144841129758825350430720 947 1827688494204259325242734707885473792 948 1993841993677373809355710590420516864 949 2159995493150488293468686472955559936 950 2326148992623602777581662355490603008 951 2492302492096717261694638238025646080 952 2741532741306388987864102061828210688 953 2990762990516060714033565885630775296 954 3323069989462289682259517650700861440 955 3655376988408518650485469415770947584 956 3987683987354747618711421180841033728 957 4319990986300976586937372945911119872 958 4652297985247205555163324710981206016 959 4984604984193434523389276476051292160 960 5483065482612777975728204123656421376 961 5981525981032121428067131771261550592 962 6646139978924579364519035301401722880 963 7310753976817037300970938831541895168 964 7975367974709495237422842361682067456 965 8639981972601953173874745891822239744 966 9304595970494411110326649421962412032 967 9969209968386869046778552952102584320 968 10966130965225555951456408247312842752 969 11963051962064242856134263542523101184 970 13292279957849158729038070602803445760 971 14621507953634074601941877663083790336 972 15950735949418990474845684723364134912 973 17279963945203906347749491783644479488 974 18609191940988822220653298843924824064 975 19938419936773738093557105904205168640 976 21932261930451111902912816494625685504 977 23926103924128485712268527085046202368 978 26584559915698317458076141205606891520 979 29243015907268149203883755326167580672 980 31901471898837980949691369446728269824 981 34559927890407812695498983567288958976 982 37218383881977644441306597687849648128 983 39876839873547476187114211808410337280 984 43864523860902223805825632989251371008 985 47852207848256971424537054170092404736 986 53169119831396634916152282411213783040 987 58486031814536298407767510652335161344 988 63802943797675961899382738893456539648 989 69119855780815625390997967134577917952 990 74436767763955288882613195375699296256 991 79753679747094952374228423616820674560 992 87729047721804447611651265978502742016 993 95704415696513942849074108340184809472 994 106338239662793269832304564822427566080 995 116972063629072596815535021304670322688 996 127605887595351923798765477786913079296 997 138239711561631250781995934269155835904 998 148873535527910577765226390751398592512 999 159507359494189904748456847233641349120 1000 175458095443608895223302531957005484032