1 1 2 7 3 19 4 47 5 76 6 151 7 197 8 335 9 424 10 632 11 727 12 1127 13 1184 14 1673 15 1894 16 2511 17 2602 18 3634 19 3611 20 4872 21 5066 22 6299 23 6349 24 8615 25 8201 26 10316 27 10630 28 13081 29 12616 30 16526 31 15377 32 19407 33 19258 34 22838 35 22322 36 28586 37 26012 38 31775 39 31622 40 37960 41 35302 42 44594 43 40679 44 49899 45 48874 46 56081 47 53017 48 67239 49 60222 50 72507 51 70246 52 82012 53 75844 54 94030 55 85502 56 102745 57 97850 58 111860 59 104431 60 131502 61 115352 62 136469 63 132479 64 152527 65 140684 66 170882 67 152627 68 182406 69 173002 70 198298 71 181477 72 225290 73 197174 74 231368 75 223769 76 254191 77 232154 78 281198 79 249641 80 299336 81 279631 82 314354 83 289339 84 356818 85 313352 86 362411 87 345670 88 394795 89 356446 90 435134 91 382306 92 449697 93 421898 94 472733 95 436886 96 531111 97 461042 98 537096 99 509713 100 581747 101 520252 102 626414 103 551669 104 650140 105 613316 106 676976 107 618247 108 754670 109 653456 110 763174 111 716006 112 813657 113 727834 114 873410 115 773474 116 899076 117 839678 118 932915 119 852458 120 1042990 121 893828 122 1030724 123 973318 124 1097509 125 992576 126 1183211 127 1032257 128 1209295 129 1122362 130 1257316 131 1132627 132 1374114 133 1188970 134 1364663 135 1298380 136 1449670 137 1295062 138 1546418 139 1352471 140 1595706 141 1464586 142 1623209 143 1474238 144 1787274 145 1547516 146 1763906 147 1664157 148 1863256 149 1665076 150 2000901 151 1732877 152 2021935 153 1873144 154 2077186 155 1889402 156 2264206 157 1947272 158 2234285 159 2098342 160 2377032 161 2106146 162 2501917 163 2178659 164 2533314 165 2365508 166 2590271 167 2342677 168 2838610 169 2428869 170 2805088 171 2612981 172 2921467 173 2603824 174 3094190 175 2725447 176 3138347 177 2892730 178 3192170 179 2883691 180 3506286 181 2981252 182 3423754 183 3196358 184 3581665 185 3209012 186 3777842 187 3290414 188 3812781 189 3536180 190 3913150 191 3502177 192 4221607 193 3613154 194 4130558 195 3899372 196 4332480 197 3842092 198 4565213 199 3960101 200 4634835 201 4233146 202 4661864 203 4216130 204 5052558 205 4363952 206 4943801 207 4629703 208 5173404 209 4590842 210 5493844 211 4719227 212 5463552 213 5035978 214 5541323 215 5033054 216 6013550 217 5148274 218 5857340 219 5472902 220 6159174 221 5425136 222 6416654 223 5569649 224 6475353 225 5991374 226 6524966 227 5874307 228 7048930 229 6030716 230 6933706 231 6445412 232 7169860 233 6351814 234 7526162 235 6569642 236 7532931 237 6933770 238 7643122 239 6854521 240 8301614 241 7027802 242 8014926 243 7483609 244 8323924 245 7465422 246 8726222 247 7569910 248 8755045 249 8039482 250 8900632 251 7938127 252 9552667 253 8136218 254 9258053 255 8705996 256 9630671 257 8520322 258 10064258 259 8746738 260 10155012 261 9269926 262 10159319 263 9130309 264 10960930 265 9415844 266 10664530 267 9909190 268 11025031 269 9768736 270 11642780 271 9987977 272 11550662 273 10628068 274 11618018 275 10529877 276 12491346 277 10665332 278 12133595 279 11320043 280 12733370 281 11133502 282 13137074 283 11372639 284 13116729 285 12148100 286 13226662 287 11896634 288 14236554 289 12113147 290 13883860 291 12824486 292 14255122 293 12619804 294 14928393 295 12984206 296 14874520 297 13663060 298 14941280 299 13417682 300 16165877 301 13721626 302 15550289 303 14475238 304 16117551 305 14348252 306 16805516 307 14514347 308 16788642 309 15351242 310 16954594 311 15088477 312 18073870 313 15381134 314 17476148 315 16464854 316 18061501 317 15977752 318 18828878 319 16295102 320 18945352 321 17207866 322 18902314 323 16907510 324 20221157 325 17365684 326 19554791 327 18189830 328 20231170 329 17912978 330 21226132 331 18187127 332 20942607 333 19234874 334 21028313 335 19006502 336 22628946 337 19193162 338 21802359 339 20264422 340 22678656 341 19900154 342 23450945 343 20295850 344 23334715 345 21533252 346 23374556 347 20951167 348 25014990 349 21315176 350 24463923 351 22533260 352 25024299 353 22055794 354 25964930 355 22614002 356 25814586 357 23738324 358 25889135 359 23198581 360 27999790 361 23591712 362 26765744 363 24894317 364 27687338 365 24577424 366 28692782 367 24782777 368 28569569 369 26163508 370 28809868 371 25677266 372 30548434 373 26017124 374 29542966 375 27645644 376 30462445 377 26876180 378 31743620 379 27291791 380 31647966 381 28758026 382 31446629 383 28164289 384 33663655 385 28946404 386 32443886 387 30177953 388 33411406 389 29507596 390 35005948 391 29973626 392 34617120 393 31559098 394 34501208 395 31142666 396 36920397 397 31364192 398 35561705 399 33128260 400 36976211 401 32321002 402 38008514 403 32823178 404 37713144 405 34864456 406 37860970 407 33819134 408 40368910 409 34292606 410 39188104 411 36092806 412 39995977 413 35412410 414 41570867 415 36112214 416 41272476 417 37695290 418 41229250 419 36867811 420 44434068 421 37397852 422 42383999 423 39397939 424 43666240 425 38794602 426 45222962 427 39133954 428 44834331 429 41092004 430 45201286 431 40124377 432 47979630 433 40685114 434 46238266 435 43133420 436 47393356 437 41832170 438 49149518 439 42398621 440 49225670 441 44771871 442 48727624 443 43567279 444 51912238 445 44516096 446 50027381 447 46422310 448 51666521 449 45360226 450 53803884 451 46004654 452 52799862 453 48315338 454 52765703 455 47745556 456 56337250 457 47826422 458 54171560 459 50339980 460 56105322 461 49092352 462 57886708 463 49733609 464 57228356 465 52678148 466 57057746 467 51032827 468 60894274 469 51843658 470 59011858 471 54301766 472 60221635 473 53065178 474 62279090 475 54143761 476 61852434 477 56478178 478 61576445 479 55065841 480 66237486 481 55785196 482 63134054 483 58733588 484 64865606 485 57620792 486 67219621 487 57869237 488 66550420 489 60763322 490 67061346 491 59305927 492 70614894 493 60048320 494 68006110 495 63668738 496 69892197 497 61686914 498 72217538 499 62250251 500 72034872 501 65343946 502 71317139 503 63758269 504 76362715 505 65041652 506 73096642 507 67749753 508 74935381 509 66065656 510 78203164 511 67044346 512 76870607 513 70257620 514 76550798 515 68979794 516 81451426 517 69281594 518 78583642 519 72637702 520 81195140 521 70846102 522 83276090 523 71664599 524 82235559 525 76019566 526 82034441 527 73338434 528 87499298 529 74164214 530 84596476 531 77894761 532 86324210 533 75888248 534 89024270 535 77326622 536 88164295 537 80454970 538 87773900 539 78732849 540 94227420 541 79316552 542 89744909 543 83180198 544 92210118 545 81741356 546 95482612 547 81983267 548 94051506 549 86082038 550 94610049 551 83810102 552 99881170 553 84958930 554 95834528 555 89531756 556 98228011 557 86559472 558 101705303 559 87536542 560 101668282 561 91813172 562 100043594 563 89385259 564 106340178 565 91068584 566 102193571 567 95108057 568 104903545 569 92271886 570 109144660 571 93247727 572 107080134 573 97732618 574 106901506 575 96001599 576 113644426 577 96216482 578 108850701 579 100833062 580 112399476 581 98519786 582 115232174 583 99324158 584 114014290 585 105025928 586 113406536 587 101303287 588 120846201 589 102360682 590 116676790 591 107229286 592 118789272 593 104439754 594 122767460 595 106684708 596 120973296 597 110526410 598 120578938 599 107640301 600 129277365 601 108721502 602 123309634 603 114043469 604 125907169 605 111884178 606 130073102 607 112008497 608 128697135 609 117672740 610 128940724 611 114290426 612 136053372 613 115361084 614 130440623 615 121797068 616 134285090 617 117632902 618 137948978 619 118779911 620 137276034 621 124574260 622 135602849 623 121452890 624 144333582 625 123258201 626 138234266 627 128146100 628 141509956 629 124655528 630 147947086 631 125818877 632 144479485 633 131737658 634 143598788 635 129257882 636 152448366 637 129882642 638 146450470 639 135699103 640 151278920 641 131892802 642 154641794 643 133130579 644 153059658 645 140492612 646 151957630 647 135629317 648 161738885 649 136995482 650 156069816 651 143718772 652 158351287 653 139435744 654 163470830 655 141852902 656 161598722 657 147485828 658 160995802 659 143312731 660 171857364 661 144620852 662 163465019 663 151460108 664 167540815 665 148905220 666 172864526 667 148611890 668 170290281 669 155502602 670 170825038 671 151397054 672 180695634 673 152637074 674 172511318 675 161242130 676 176560431 677 155373532 678 182124398 679 157215178 680 181425920 681 164016826 682 178866658 683 159539239 684 189891121 685 162239312 686 182422450 687 168388070 688 186403899 689 163855772 690 193523668 691 165208427 692 189300972 693 173709278 694 188319683 695 169445246 696 200111950 697 169585244 698 191592980 699 177362182 700 198111331 701 172481752 702 202520540 703 173991190 704 199862059 705 183432836 706 198252926 707 177466994 708 210263970 709 178451756 710 203263834 711 186899651 712 206540410 713 181509458 714 213354916 715 184716988 716 209676351 717 191412490 718 208529465 719 186105961 720 223644974 721 188214466 722 212064042 723 196255718 724 216779584 725 192357516 726 223753593 727 192384557 728 221524010 729 201459574 730 220919656 731 195619406 732 232366414 733 197185064 734 222775613 735 208458282 736 228201441 737 200582714 738 235165448 739 202064771 740 233331756 741 211403620 742 230814394 743 205362229 744 244405330 745 208689476 746 233875856 747 216735253 748 239280342 749 210993818 750 248485276 751 212064377 752 243376877 753 221700538 754 241599340 755 217202402 756 257075140 757 217185572 758 245338835 759 227232164 760 253225310 761 220645102 762 258499634 763 223042210 764 254710389 765 234696644 766 253185221 767 226008590 768 268872359 769 227673986 770 260200436 771 237974566 772 262791742 773 231243724 774 271264877 775 234940027 776 267357070 777 244292164 778 265265720 779 236706902 780 283504956 781 238676954 782 269455234 783 249611020 784 276580512 785 244123772 786 283688642 787 244031387 788 279463656 789 255026122 790 279959410 791 248497706 792 295406605 793 249769588 794 281962508 795 262986092 796 288057721 797 253448392 798 297792340 799 255416018 800 295373907 801 267191596 802 290567414 803 259411118 804 307852258 805 264049396 806 295081522 807 272873350 808 301796920 809 265064806 810 313396292 811 267034727 812 306682890 813 279002378 814 304037926 815 273182534 816 322528526 817 273047290 818 308298890 819 286575142 820 317431464 821 277030852 822 324459854 823 279059549 824 320073865 825 294121758 826 318363490 827 283146607 828 336714339 829 285205016 830 324651646 831 297938726 832 329716892 833 290264196 834 338871170 835 293782802 836 333983202 837 304868660 838 331459175 839 295646821 840 355539860 841 297777917 842 336226184 843 311027398 844 343345999 845 304600944 846 354179231 847 305306671 848 348928064 849 317713082 850 348773838 851 308541986 852 366315474 853 310689044 854 351833386 855 327588506 856 358811995 857 315078622 858 369413236 859 317288831 860 366162342 861 332348852 862 360747869 863 321740209 864 383288430 865 326585324 866 365791046 867 338413817 868 374573402 869 328745402 870 387762940 871 330921286 872 379301260 873 345875264 874 376105810 875 339053572 876 398136046 877 337647632 878 381202145 879 352581862 880 393351622 881 342287002 882 402500757 883 344622539 884 394753128 885 362742980 886 391713011 887 349325437 888 415438510 889 352725298 890 400232920 891 368002987 892 405291397 893 356516330 894 417356750 895 361742966 896 412786265 897 374884196 898 407838830 899 363718442 900 435830036 901 366200696 902 413631478 903 383373028 904 422590390 905 373999652 906 434382002 907 373482647 908 427484631 909 390433498 910 429268004 911 378443977 912 450180450 913 381231098 914 430020098 915 400880108 916 438878776 917 387100874 918 452584220 919 388498061 920 449037290 921 405553466 922 441406124 923 393773858 924 468929076 925 399371512 926 447173741 927 414080303 928 457265220 929 401314066 930 473603092 931 405159621 932 462270882 933 421606858 934 458859263 935 412823164 936 487344130 937 411767462 938 466143922 939 429790022 940 478089906 941 417061552 942 488222894 943 419767178 944 481285571 945 443508680 946 477135202 947 425087467 948 504542290 949 427983832 950 486822525 951 446472646 952 495062930 953 433215694 954 507792182 955 439450202 956 498894861 957 455338340 958 495133685 959 442742138 960 529191982 961 444228978 962 501600964 963 464200129 964 511519414 965 453394904 966 528072292 967 452583077 968 519198630 969 472465460 970 518097808 971 458220727 972 544576277 973 462409690 974 520348793 975 485243122 976 531885972 977 466764682 978 546338498 979 469993262 980 543318930 981 490709486 982 533271179 983 475414189 984 565186030 985 482163092 986 539946520 987 500568884 988 551003390 989 484216922 990 572441338 991 487112177 992 558496869 993 508253498 994 554678026 995 496992626 996 585090786 997 496010492 998 559754255 999 518245580 1000 576587960