0 1 1 2 2 1 3 2 4 3 5 2 6 4 7 4 8 4 9 6 10 7 11 8 12 8 13 10 14 11 15 14 16 16 17 16 18 20 19 22 20 24 21 28 22 32 23 34 24 39 25 44 26 48 27 54 28 60 29 66 30 73 31 82 32 88 33 98 34 108 35 118 36 132 37 144 38 156 39 172 40 188 41 204 42 224 43 244 44 265 45 290 46 316 47 340 48 372 49 404 50 436 51 474 52 513 53 554 54 600 55 650 56 700 57 756 58 816 59 878 60 948 61 1022 62 1096 63 1182 64 1272 65 1364 66 1468 67 1576 68 1688 69 1814 70 1945 71 2082 72 2232 73 2390 74 2556 75 2736 76 2928 77 3126 78 3344 79 3572 80 3811 81 4072 82 4344 83 4630 84 4940 85 5266 86 5608 87 5976 88 6364 89 6770 90 7208 91 7670 92 8152 93 8670 94 9216 95 9788 96 10400 97 11044 98 11720 99 12444 100 13204 101 14002 102 14851 103 15746 104 16684 105 17684 106 18736 107 19836 108 21008 109 22240 110 23532 111 24904 112 26344 113 27856 114 29459 115 31142 116 32908 117 34776 118 36740 119 38798 120 40976 121 43262 122 45656 123 48188 124 50844 125 53628 126 56568 127 59650 128 62880 129 66286 130 69860 131 73602 132 77544 133 81678 134 86008 135 90566 136 95344 137 100344 138 105604 139 111118 140 116887 141 122954 142 129304 143 135952 144 142936 145 150246 146 157896 147 165924 148 174328 149 183118 150 192340 151 201990 152 212076 153 222656 154 233721 155 245286 156 257408 157 270080 158 283324 159 297196 160 311696 161 326846 162 342704 163 359276 164 376584 165 394696 166 413616 167 433368 168 454032 169 475610 170 498132 171 521682 172 546264 173 571916 174 598728 175 626708 176 655900 177 686392 178 718208 179 751392 180 786044 181 822188 182 859872 183 899212 184 940233 185 982994 186 1027616 187 1074128 188 1122604 189 1173170 190 1225868 191 1280774 192 1338024 193 1397676 194 1459808 195 1524578 196 1592044 197 1662296 198 1735508 199 1811746 200 1891117 201 1973804 202 2059884 203 2149482 204 2242796 205 2339916 206 2440980 207 2546200 208 2655688 209 2769596 210 2888156 211 3011496 212 3139776 213 3273266 214 3412100 215 3556468 216 3706656 217 3862816 218 4025168 219 4194016 220 4369544 221 4551988 222 4741680 223 4938834 224 5143712 225 5356680 226 5577972 227 5807878 228 6046808 229 6295022 230 6552848 231 6820728 232 7098952 233 7387890 234 7688025 235 7999688 236 8323284 237 8659336 238 9008228 239 9370404 240 9746440 241 10136760 242 10541856 243 10962366 244 11398760 245 11851588 246 12321544 247 12809148 248 13315020 249 13839914 250 14384416 251 14949208 252 15535111 253 16142790 254 16772988 255 17426614 256 18104404 257 18807172 258 19535928 259 20291478 260 21074736 261 21886796 262 22728552 263 23601024 264 24505400 265 25442686 266 26413996 267 27420632 268 28463712 269 29544466 270 30664324 271 31824518 272 33026400 273 34271548 274 35561320 275 36897210 276 38280940 277 39714008 278 41198072 279 42735012 280 44326488 281 45974322 282 47680560 283 49447056 284 51275804 285 53169052 286 55128840 287 57157352 288 59257068 289 61430222 290 63679231 291 66006796 292 68415376 293 70907642 294 73486540 295 76154790 296 78915312 297 81771328 298 84725844 299 87782060 300 90943508 301 94213486 302 97595504 303 101093434 304 104710896 305 108451752 306 112320224 307 116320288 308 120456192 309 124732542 310 129153715 311 133724358 312 138449504 313 143333966 314 148382836 315 153601616 316 158995584 317 164570304 318 170331808 319 176285876 320 182438608 321 188796586 322 195366136 323 202153958 324 209167220 325 216412872 326 223898232 327 231631118 328 239619164 329 247870360 330 256393256 331 265196188 332 274287896 333 283677724 334 293374784 335 303388642 336 313729476 337 324407256 338 335432444 339 346816136 340 358569240 341 370703178 342 383230040 343 396161768 344 409510824 345 423290396 346 437513524 347 452193804 348 467345628 349 482983228 350 499121452 351 515775972 352 532962315 353 550696700 354 568996188 355 587877738 356 607359028 357 627458628 358 648195064 359 669587592 360 691656448 361 714421824 362 737904696 363 762127118 364 787111088 365 812879480 366 839456272 367 866865440 368 895131916 369 924281776 370 954341160 371 985337200 372 1017298256 373 1050252814 374 1084230401 375 1119261872 376 1155378228 377 1192611598 378 1230995548 379 1270563810 380 1311351348 381 1353394636 382 1396730376 383 1441396614 384 1487432976 385 1534879398 386 1583777240 387 1634169536 388 1686099748 389 1739612816 390 1794755500 391 1851575038 392 1910120256 393 1970441960 394 2032591468 395 2096621848 396 2162588244 397 2230546404 398 2300553992 399 2372670846 400 2446957544 401 2523476674 402 2602293168 403 2683472832 404 2767083596 405 2853195922 406 2941881232 407 3033213244 408 3127268400 409 3224124214 410 3323860680 411 3426560678 412 3532308304 413 3641190354 414 3753296672 415 3868718488 416 3987549920 417 4109888336 418 4235832704 419 4365485044 420 4498950889 421 4636337524 422 4777755512 423 4923319222 424 5073144924 425 5227352446 426 5386065652 427 5549410528 428 5717516920 429 5890518944 430 6068553108 431 6251760036 432 6440284920 433 6634275646 434 6833884464 435 7039268564 436 7250588056 437 7468007760 438 7691697820 439 7921831544 440 8158587352 441 8402149308 442 8652704984 443 8910447468 444 9175575857 445 9448293138 446 9728808176 447 10017336296 448 10314097112 449 10619316524 450 10933227368 451 11256067158 452 11588080156 453 11929518102 454 12280637808 455 12641703368 456 13012986852 457 13394765868 458 13787325912 459 14190960960 460 14605971080 461 15032664768 462 15471359616 463 15922379910 464 16386058924 465 16862739734 466 17352772656 467 17856517672 468 18374345320 469 18906633952 470 19453772360 471 20016160582 472 20594207192 473 21188332008 474 21798966844 475 22426552842 476 23071543168 477 23734403862 478 24415611124 479 25115654030 480 25835035484 481 26574269380 482 27333883440 483 28114420256 484 28916434284 485 29740494862 486 30587187232 487 31457109496 488 32350875788 489 33269117222 490 34212478896 491 35181623064 492 36177230184 493 37199995912 494 38250634261 495 39329878788 496 40438479456 497 41577205932 498 42746848888 499 43948216664 500 45182138808 501 46449467320 502 47751073304 503 49087850690 504 50460717384 505 51870612000 506 53318497572 507 54805362852 508 56332219008 509 57900103332 510 59510080736 511 61163240258 512 62860698992 513 64603603656 514 66393126956 515 68230471732 516 70116872504 517 72053591848 518 74041924696 519 76083199870 520 78178776467 521 80330048258 522 82538445304 523 84805430366 524 87132503312 525 89521202930 526 91973103192 527 94489817844 528 97073002404 529 99724350188 530 102445597220 531 105238524198 532 108104952520 533 111046749438 534 114065829944 535 117164152926 536 120343726332 537 123606609248 538 126954908056 539 130390781630 540 133916443664 541 137534158644 542 141246247336 543 145055089248 544 148963118428 545 152972829284 546 157086779040 547 161307583568 548 165637923452 549 170080546452 550 174638263408 551 179313954408 552 184110571456 553 189031134394 554 194078737148 555 199256550658 556 204567818676 557 210015864296 558 215604093092 559 221335988746 560 227215119944 561 233245143574 562 239429800368 563 245772922152 564 252278435028 565 258950355142 566 265792796096 567 272809972344 568 280006195048 569 287385879566 570 294953549228 571 302713831024 572 310671463464 573 318831300626 574 327198307655 575 335777569120 576 344574293084 577 353593806742 578 362841565124 579 372323155226 580 382044291840 581 392010826416 582 402228751544 583 412704196830 584 423443437992 585 434452901704 586 445739161380 587 457308946720 588 469169148872 589 481326816106 590 493789163872 591 506563580136 592 519657621160 593 533079022044 594 546835702180 595 560935761244 596 575387490048 597 590199376340 598 605380101012 599 620938549144 600 636883816344 601 653225204886 602 669972235303 603 687134653162 604 704722425080 605 722745751044 606 741215071340 607 760141062824 608 779534651800 609 799407021158 610 819769606964 611 840634111710 612 862012511976 613 883917055236 614 906360273476 615 929354991490 616 952914323692 617 977051688424 618 1001780816784 619 1027115749456 620 1053070851820 621 1079660823088 622 1106900693488 623 1134805840066 624 1163391996180 625 1192675249076 626 1222672056256 627 1253399255596 628 1284874063264 629 1317114090642 630 1350137355176 631 1383962278466 632 1418607704000 633 1454092908768 634 1490437601420 635 1527661941014 636 1565786549120 637 1604832508424 638 1644821382432 639 1685775228002 640 1727716594612 641 1770668544722 642 1814654667168 643 1859699076954 644 1905826436296 645 1953061969050 646 2001431460736 647 2050961280740 648 2101678397600 649 2153610379342 650 2206785416928 651 2261232340224 652 2316980619024 653 2374060387632 654 2432502461592 655 2492338339480 656 2553600228472 657 2616321062168 658 2680534503112 659 2746274969364 660 2813577653551 661 2882478525954 662 2953014362416 663 3025222764632 664 3099142163740 665 3174811849800 666 3252271993080 667 3331563648544 668 3412728786908 669 3495810316872 670 3580852090752 671 3667898936826 672 3756996682992 673 3848192163480 674 3941533252484 675 4037068889510 676 4134849086864 677 4234924965082 678 4337348779884 679 4442173930472 680 4549454996996 681 4659247768824 682 4771609254208 683 4886597719660 684 5004272719644 685 5124695107770 686 5247927077884 687 5374032195688 688 5503075411368 689 5635123102522 690 5770243107873 691 5908504741142 692 6049978836312 693 6194737783398 694 6342855543644 695 6494407697308 696 6649471481364 697 6808125806472 698 6970451307300 699 7136530382202 700 7306447212212 701 7480287813748 702 7658140080724 703 7840093805648 704 8026240734696 705 8216674612610 706 8411491205644 707 8610788359580 708 8814666047456 709 9023226394336 710 9236573738720 711 9454814682760 712 9678058119552 713 9906415297852 714 10139999874944 715 10378927946774 716 10623318115700 717 10873291546760 718 11128972000516 719 11390485904102 720 11657962411100 721 11931533436984 722 12211333734096 723 12497500955130 724 12790175691384 725 13089501551920 726 13395625230588 727 13708696547650 728 14028868533268 729 14356297498168 730 14691143079008 731 15033568326076 732 15383739778264 733 15741827512272 734 16108005234648 735 16482450361510 736 16865344071428 737 17256871402528 738 17657221337096 739 18066586858278 740 18485165052712 741 18913157199874 742 19350768833352 743 19798209849156 744 20255694599956 745 20723441961478 746 21201675446308 747 21690623303888 748 22190518592112 749 22701599296892 750 23224108438440 751 23758294147898 752 24304409793609 753 24862714093768 754 25433471198400 755 26016950822856 756 26613428366752 757 27223185002232 758 27846507814784 759 28483689928918 760 29135030603148 761 29800835378182 762 30481416210216 763 31177091572866 764 31888186613128 765 32615033292810 766 33357970497512 767 34117344201240 768 34893507616324 769 35686821309756 770 36497653377148 771 37326379601180 772 38173383576264 773 39039056892258 774 39923799301772 775 40828018853920 776 41752132087808 777 42696564209830 778 43661749236868 779 44648130199942 780 45656159332392 781 46686298222480 782 47739018028496 783 48814799678130 784 49914134031025 785 51037522106194 786 52185475292632 787 53358515523208 788 54557175514672 789 55781998990240 790 57033540865560 791 58312367501612 792 59619056940560 793 60954199104220 794 62318396060620 795 63712262273952 796 65136424815896 797 66591523647132 798 68078211882036 799 69597156013532 800 71149036210576 801 72734546597970 802 74354395496144 803 76009305735300 804 77700014951104 805 79427275840510 806 81191856492976 807 82994540703544 808 84836128245488 809 86717435219424 810 88639294385016 811 90602555450866 812 92608085443192 813 94656769057016 814 96749508964152 815 98887226202866 816 101070860549004 817 103301370843896 818 105579735405876 819 107906952422398 820 110284040299300 821 112712038094724 822 115192005934272 823 117725025382472 824 120312199900368 825 122954655285166 826 125653540064640 827 128410025980502 828 131225308453512 829 134100607002254 830 137037165753780 831 140036253935162 832 143099166318720 833 146227223761172 834 149421773723120 835 152684190742340 836 156015877002636 837 159418262883376 838 162892807462344 839 166440999115738 840 170064356099760 841 173764427084122 842 177542791785600 843 181401061583328 844 185340880084492 845 189363923793686 846 193471902763032 847 197666561192800 848 201949678138200 849 206323068196192 850 210788582143353 851 215348107681440 852 220003570163820 853 224756933272328 854 229610199803740 855 234565412438264 856 239624654456908 857 244790050572036 858 250063767739868 859 255448015920662 860 260945048955956 861 266557165426914 862 272286709460600 863 278136071656098 864 284107689991280 865 290204050677936 866 296427689138872 867 302781190966568 868 309267192829648 869 315888383503694 870 322647504884848 871 329547352949970 872 336590778844864 873 343780689955634 874 351120050925384 875 358611884803322 876 366259274176396 877 374065362246518 878 382033354043656 879 390166517620896 880 398468185195936 881 406941754430912 882 415590689695296 883 424418523274958 884 433428856722203 885 442625362190648 886 452011783714800 887 461591938635128 888 471369719008484 889 481349092962052 890 491534106197904 891 501928883482250 892 512537630079008 893 523364633337664 894 534414264265720 895 545690979046516 896 557199320714200 897 568943920814956 898 580929501013236 899 593160874858730 900 605642949541292 901 618380727589916 902 631379308737516 903 644643891774398 904 658179776345048 905 671992364916202 906 686087164733672 907 700469789723120 908 715145962566848 909 730121516769362 910 745402398668272 911 760994669624882 912 776904508205352 913 793138212307566 914 809702201471412 915 826603019182304 916 843847335119424 917 861441947593328 918 879393785978024 919 897709913087136 920 916397527746116 921 935463967358940 922 954916710420344 923 974763379229400 924 995011742598116 925 1015669718507476 926 1036745376969156 927 1058246942884832 928 1080182798853408 929 1102561488188790 930 1125391717938356 931 1148682361848774 932 1172442463549352 933 1196681239737738 934 1221408083313024 935 1246632566733774 936 1272364445379200 937 1298613660859672 938 1325390344558400 939 1352704821177504 940 1380567612235768 941 1408989439803112 942 1437981230242464 943 1467554117904598 944 1497719449065540 945 1528488785875128 946 1559873910258760 947 1591886828069588 948 1624539773254628 949 1657845211974320 950 1691815846981452 951 1726464622015476 952 1761804726152820 953 1797849598424286 954 1834612932449519 955 1872108681031060 956 1910351061021808 957 1949354558213820 958 1989133932188660 959 2029704221448164 960 2071080748571576 961 2113279125334852 962 2156315258120176 963 2200205353355048 964 2244965922915056 965 2290613789827156 966 2337166094004860 967 2384640297950904 968 2433054192769280 969 2482425904212376 970 2532773898699740 971 2584116989654440 972 2636474343879808 973 2689865487910798 974 2744310314691744 975 2799829090300482 976 2856442460649216 977 2914171458522796 978 2973037510668316 979 3033062444863844 980 3094268497336744 981 3156678320237076 982 3220314989094944 983 3285202010638592 984 3351363330671608 985 3418823341940074 986 3487606892370324 987 3557739293372680 988 3629246328139624 989 3702154260325120 990 3776489842797915 991 3852280326392352 992 3929553469053936 993 4008337545065264 994 4088661354273364 995 4170554231726386 996 4254046057395880 997 4339167265907324 998 4425948856693064 999 4514422404236976 1000 4604620068335056