0 0 1 1 2 3 3 7 4 10 5 21 6 21 7 43 8 36 9 57 10 63 11 111 12 70 13 157 14 129 15 147 16 136 17 273 18 171 19 343 20 210 21 301 22 333 23 507 24 252 25 505 26 471 27 495 28 430 29 813 30 441 31 931 32 528 33 777 34 819 35 903 36 570 37 1333 38 1029 39 1099 40 756 41 1641 42 903 43 1807 44 1110 45 1197 46 1521 47 2163 48 952 49 2065 50 1515 51 1911 52 1570 53 2757 54 1485 55 2331 56 1548 57 2401 58 2439 59 3423 60 1470 61 3661 62 2793 63 2451 64 2080 65 3297 66 2331 67 4423 68 2730 69 3549 70 2709 71 4971 72 2052 73 5257 74 3999 75 3535 76 3430 77 4773 78 3297 79 6163 80 2856 81 4401 82 4923 83 6807 84 3010 85 5733 86 5421 87 5691 88 3996 89 7833 90 3591 91 6751 92 5070 93 6517 94 6489 95 7203 96 3696 97 9313 98 6195 99 6327 100 5050 101 10101 102 5733 103 10507 104 5652 105 6321 106 8271 107 11343 108 4950 109 11773 110 6993 111 9331 112 5848 113 12657 114 7203 115 10647 116 8130 117 8949 118 10269 119 11739 120 5292 121 13321 122 10983 123 11487 124 9310 125 12525 126 7353 127 16003 128 8256 129 12649 130 9891 131 17031 132 7770 133 14749 134 13269 135 10395 136 9828 137 18633 138 10647 139 19183 140 9030 141 15141 142 14913 143 17427 144 7752 145 17073 146 15771 147 14455 148 13330 149 22053 150 10605 151 22651 152 12348 153 15561 154 14319 155 19551 156 10990 157 24493 158 18489 159 19299 160 11088 161 21801 162 13203 163 26407 164 16410 165 16317 166 20421 167 27723 168 10836 169 26377 170 17199 171 19551 172 18070 173 29757 174 17073 175 21715 176 15096 177 23961 178 23499 179 31863 180 11970 181 32581 182 20253 183 25627 184 18252 185 27993 186 19551 187 30303 188 21630 189 21285 190 21609 191 36291 192 14560 193 37057 194 27939 195 23079 196 20650 197 38613 198 18981 199 39403 200 18180 201 30961 202 30303 203 34959 204 19110 205 34461 206 31521 207 28899 208 21352 209 38073 210 18963 211 44311 212 27570 213 34797 214 34029 215 37947 216 17820 217 40033 218 35319 219 36799 220 23310 221 42861 222 27993 223 49507 224 22704 225 28785 226 37971 227 51303 228 24010 229 52213 230 31941 231 33411 232 29268 233 54057 234 26847 235 45423 236 34230 237 43141 238 35217 239 56883 240 19992 241 57841 242 39963 243 39447 244 36610 245 43365 246 34461 247 53851 248 33516 249 47649 250 37575 251 62751 252 24510 253 56277 254 48009 255 40131 256 32896 257 65793 258 37947 259 57319 260 32970 261 46341 262 51093 263 68907 264 27972 265 57897 266 44247 267 54831 268 44230 269 72093 270 31185 271 73171 272 37128 273 47257 274 55899 275 56055 276 35490 277 76453 278 57549 279 53067 280 32508 281 78681 282 45423 283 79807 284 49710 285 50421 286 52281 287 70563 288 30096 289 78625 290 51219 291 65191 292 52570 293 85557 294 43365 295 71883 296 47988 297 54945 298 66159 299 79599 300 35350 301 77701 302 67953 303 70707 304 46648 305 76881 306 46683 307 93943 308 47730 309 73549 310 58653 311 96411 312 39564 313 97657 314 73479 315 51471 316 61630 317 100173 318 57897 319 90243 320 43680 321 79401 322 65403 323 93639 324 44010 325 79285 326 79221 327 82411 328 59076 329 93009 330 48951 331 109231 332 68070 333 75981 334 83169 335 92883 336 40936 337 113233 338 79131 339 88599 340 57330 341 103341 342 58653 343 100891 344 65052 345 74529 346 89271 347 120063 348 56910 349 121453 350 65145 351 77715 352 58608 353 124257 354 71883 355 104391 356 78330 357 82173 358 95589 359 128523 360 43092 361 123481 362 97743 363 93247 364 67510 365 110397 366 76881 367 134323 368 68952 369 93537 370 83979 371 118551 372 65170 373 138757 374 90909 375 87675 376 77868 377 127641 378 63855 379 143263 380 72030 381 112021 382 108873 383 146307 384 57792 385 100233 386 111171 387 102999 388 93130 389 150933 390 69237 391 138411 392 74340 393 119217 394 115839 395 129423 396 63270 397 157213 398 118209 399 103243 400 68680 401 160401 402 92883 403 146167 404 101010 405 92421 406 104877 407 147963 408 68796 409 166873 410 103383 411 130431 412 105070 413 147189 414 86697 415 142947 416 82896 417 134281 418 114219 419 175143 420 63210 421 176821 422 132933 423 123291 424 99252 425 137865 426 104391 427 157423 428 113430 429 121989 430 113841 431 185331 432 67320 433 187057 434 120099 435 119511 436 117730 437 173901 438 110397 439 192283 440 83916 441 117705 442 128583 443 195807 444 93310 445 164493 446 148521 447 154371 448 89440 449 201153 450 86355 451 182151 452 126570 453 158557 454 153909 455 141771 456 86436 457 208393 458 156639 459 135135 460 106470 461 212061 462 100233 463 213907 464 110568 465 136857 466 162171 467 217623 468 89490 469 190189 470 136269 471 171451 472 123228 473 200577 474 129423 475 173215 476 117390 477 157149 478 170649 479 228963 480 77616 481 209281 482 173523 483 152607 484 133210 485 195573 486 118341 487 236683 488 131796 489 184849 490 130095 491 240591 492 114870 493 221949 494 161553 495 132867 496 126616 497 213753 498 142947 499 248503 500 125250 501 194061 502 188253 503 252507 504 88236 505 212121 506 168831 507 184639 508 160030 509 258573 510 120393 511 226051 512 131328 513 169785 514 197379 515 220647 516 126490 517 240093 518 171957 519 208299 520 118692 521 270921 522 139023 523 273007 524 170310 525 152005 526 206721 527 254163 528 105672 529 267697 530 173691 531 195111 532 147490 533 257637 534 164493 535 238203 536 159228 537 223041 538 216279 539 229215 540 103950 541 292141 542 219513 543 228067 544 144144 545 247233 546 141771 547 298663 548 186330 549 208677 550 168165 551 278859 552 127764 553 265009 554 229359 555 195951 556 191830 557 309693 558 159201 559 283699 560 122808 561 212121 562 236043 563 316407 564 151410 565 265797 566 239421 567 189243 568 178956 569 323193 570 151263 571 325471 572 174270 573 254037 574 211689 575 256035 576 118560 577 332353 578 235875 579 259399 580 170730 581 292701 582 195573 583 306027 584 189252 585 187929 586 256671 587 343983 588 144550 589 319333 590 215649 591 270291 592 181288 593 351057 594 164835 595 246519 596 220530 597 275821 598 238797 599 358203 600 127260 601 360601 602 233103 603 252111 604 226510 605 279741 606 212121 607 367843 608 181104 609 244713 610 230643 611 339591 612 155610 613 375157 614 281829 615 241227 616 171828 617 380073 618 220647 619 382543 620 195510 621 250965 622 289233 623 336819 624 149464 625 312625 626 292971 627 266511 628 244930 629 363909 630 154413 631 397531 632 221868 633 310177 634 300519 635 336063 636 192990 637 324205 638 270729 639 283347 640 173376 641 410241 642 238203 643 412807 644 218010 645 265629 646 280917 647 417963 648 158436 649 379953 650 237855 651 280231 652 264070 653 425757 654 247233 655 357651 656 223176 657 299649 658 279027 659 433623 660 163170 661 436261 662 327693 663 300027 664 245052 665 309729 666 227943 667 412191 668 277230 669 346549 670 278649 671 406371 672 158928 673 452257 674 339699 675 249975 676 263770 677 457653 678 265797 679 400459 680 206388 681 359121 682 310023 683 465807 684 195510 685 391293 686 302673 687 365491 688 245752 689 432849 690 223587 691 476791 692 297570 693 272061 694 360189 695 402843 696 204876 697 447993 698 364359 699 378399 700 217150 701 490701 702 233145 703 457219 704 230880 705 317961 706 372771 707 434343 708 239610 709 501973 710 313173 711 351291 712 281988 713 472017 714 246519 715 365967 716 318630 717 398181 718 385569 719 516243 720 162792 721 451801 722 370443 723 404887 724 325810 725 410565 726 279741 727 527803 728 243036 729 354537 730 331191 731 493311 732 256270 733 536557 734 402969 735 303555 736 267696 737 490953 738 280611 739 545383 740 279930 741 376957 742 355653 743 551307 744 234612 745 463113 746 416271 747 387999 748 303030 749 487749 750 263025 751 563251 752 294168 753 439257 754 382923 755 475671 756 212850 757 572293 758 429789 759 393939 760 259308 761 578361 762 336063 763 506239 764 362910 765 326781 766 438921 767 537411 768 230272 769 590593 770 300699 771 460551 772 370570 773 596757 774 308997 775 470155 776 335268 777 401233 778 452799 779 562863 780 230790 781 551781 782 415233 783 402435 784 280840 785 514353 786 357651 787 618583 788 386130 789 482349 790 388269 791 544251 792 227772 793 574777 794 471639 795 405279 796 394030 797 634413 798 309729 799 590499 800 266640 801 446481 802 481203 803 583527 804 309610 805 457821 806 438501 807 504651 808 363636 809 653673 810 277263 811 656911 812 349590 813 512197 814 443889 815 554547 816 259896 817 619801 818 500619 819 384807 820 344610 821 673221 822 391293 823 676507 824 378252 825 392385 826 441567 827 683103 828 288990 829 686413 830 428841 831 535171 832 326560 833 563745 834 402843 835 582183 836 380730 837 460845 838 525429 839 703083 840 227556 841 682921 842 530463 843 550767 844 443110 845 553917 846 369873 847 572803 848 374952 849 558649 850 413595 851 675831 852 347970 853 726757 854 472269 855 410571 856 408348 857 733593 858 365967 859 737023 860 379470 861 493941 862 555993 863 743907 864 261360 865 624897 866 561171 867 550375 868 400330 869 684093 870 358533 871 694411 872 423828 873 530841 874 521703 875 538575 876 367990 877 768253 878 576849 879 598899 880 317016 881 775281 882 353115 883 778807 884 428610 885 503181 886 587421 887 785883 888 335916 889 688129 890 493479 891 488511 892 495070 893 741909 894 463113 895 669123 896 355008 897 557193 898 603459 899 756903 900 287850 901 752661 902 546453 903 543907 904 455652 905 684201 906 475671 907 821743 908 513030 909 575757 910 425313 911 829011 912 326536 913 755577 914 625179 915 538167 916 522130 917 732333 918 405405 919 843643 920 383292 921 657601 922 636183 923 780447 924 334110 925 673165 926 641721 927 598899 928 429264 929 862113 930 410571 931 708295 932 540570 933 674877 934 652869 935 636363 936 322164 937 877033 938 570567 939 683599 940 454230 941 884541 942 514353 943 831987 944 465528 945 446985 946 601731 947 895863 948 431410 949 825349 950 519645 951 701211 952 422604 953 907257 954 471447 955 762111 956 568830 957 631701 958 686889 959 801219 960 305760 961 893761 962 627843 963 646551 964 578410 965 778197 966 457821 967 934123 968 479556 969 655473 970 586719 971 941871 972 394470 973 824869 974 710049 975 554995 976 497896 977 953553 978 554547 979 869463 980 433650 981 671061 982 721773 983 965307 984 413532 985 810873 986 665847 987 651063 988 538510 989 916149 990 398601 991 981091 992 491568 993 764617 994 641259 995 827463 996 476490 997 993013 998 745509 999 659835 1000 450900