0 4 1 1 2 2 3 3 4 21 5 5 6 15 7 7 8 33 9 22 10 66 11 11 12 77 13 13 14 39 15 26 16 57 17 17 18 51 19 19 20 69 21 46 22 95 23 23 24 145 25 465 26 155 27 435 28 93 29 29 30 87 31 31 32 185 33 777 34 259 35 555 36 222 37 37 38 111 39 74 40 129 41 41 42 123 43 43 44 141 45 94 46 215 47 47 48 265 49 1113 50 371 51 795 52 318 53 53 54 159 55 106 56 177 57 118 58 354 59 59 60 366 61 61 62 183 63 122 64 201 65 134 66 355 67 67 68 213 69 142 70 335 71 71 72 438 73 73 74 219 75 146 76 237 77 158 78 474 79 79 80 249 81 166 82 498 83 83 84 581 85 1245 86 415 87 1743 88 534 89 89 90 267 91 178 92 445 93 1869 94 623 95 1335 96 505 97 97 98 291 99 194 100 309 101 101 102 303 103 103 104 321 105 214 106 642 107 107 108 654 109 109 110 327 111 218 112 678 113 113 114 339 115 226 116 565 117 2373 118 791 119 1695 120 889 121 1905 122 635 123 2667 124 381 125 254 126 762 127 127 128 393 129 262 130 786 131 131 132 917 133 1965 134 655 135 2751 136 417 137 137 138 411 139 139 140 685 141 2085 142 695 143 2055 144 745 145 2265 146 755 147 2235 148 453 149 149 150 447 151 151 152 785 153 3297 154 1099 155 2355 156 942 157 157 158 471 159 314 160 489 161 326 162 835 163 163 164 501 165 334 166 815 167 167 168 865 169 3633 170 1211 171 2595 172 1038 173 173 174 519 175 346 176 537 177 358 178 1074 179 179 180 1086 181 181 182 543 183 362 184 1337 185 2865 186 955 187 4011 188 573 189 382 190 1146 191 191 192 985 193 193 194 579 195 386 196 597 197 197 198 591 199 199 200 2561 201 6369 202 2123 203 7683 204 2189 205 6501 206 2167 207 6567 208 633 209 422 210 1266 211 211 212 1477 213 3165 214 1055 215 4431 216 1561 217 3345 218 1115 219 4683 220 669 221 446 222 1338 223 223 224 681 225 454 226 1362 227 227 228 1374 229 229 230 687 231 458 232 1398 233 233 234 699 235 466 236 717 237 478 238 1434 239 239 240 1446 241 241 242 723 243 482 244 1205 245 5061 246 1687 247 3615 248 753 249 502 250 1506 251 251 252 1757 253 3765 254 1255 255 5271 256 1542 257 257 258 771 259 514 260 789 261 526 262 1578 263 263 264 1345 265 4065 266 1355 267 4035 268 813 269 269 270 807 271 271 272 1385 273 5817 274 1939 275 4155 276 1662 277 277 278 831 279 554 280 849 281 281 282 843 283 283 284 1405 285 4245 286 1415 287 4215 288 1465 289 6153 290 2051 291 4395 292 1758 293 293 294 879 295 586 296 3809 297 17841 298 5947 299 11427 300 5389 301 9669 302 3223 303 16167 304 921 305 614 306 1555 307 307 308 933 309 622 310 1535 311 311 312 1585 313 313 314 939 315 626 316 1565 317 317 318 951 319 634 320 3641 321 19209 322 6403 323 10923 324 8606 325 12909 326 4303 327 25487 328 993 329 662 330 1986 331 331 332 2317 333 4965 334 1655 335 6951 336 2022 337 337 338 1011 339 674 340 1685 341 7077 342 2359 343 5055 344 1041 345 694 346 2082 347 347 348 2094 349 349 350 1047 351 698 352 2118 353 353 354 1059 355 706 356 1077 357 718 358 2154 359 359 360 2569 361 5505 362 1835 363 7707 364 1101 365 734 366 2202 367 367 368 1865 369 7833 370 2611 371 5595 372 2238 373 373 374 1119 375 746 376 1137 377 758 378 1915 379 379 380 1149 381 766 382 1895 383 383 384 1945 385 8169 386 2723 387 5835 388 2334 389 389 390 1167 391 778 392 1985 393 8337 394 2779 395 5955 396 2382 397 397 398 1191 399 794 400 2406 401 401 402 1203 403 802 404 2005 405 8421 406 2807 407 6015 408 2454 409 409 410 1227 411 818 412 2045 413 8589 414 2863 415 6135 416 1257 417 838 418 2514 419 419 420 2526 421 421 422 1263 423 842 424 3017 425 6465 426 2155 427 9051 428 1293 429 862 430 2586 431 431 432 2598 433 433 434 1299 435 866 436 1317 437 878 438 2634 439 439 440 1329 441 886 442 2658 443 443 444 3101 445 6645 446 2215 447 9303 448 2694 449 449 450 1347 451 898 452 2245 453 9429 454 3143 455 6735 456 2305 457 457 458 1371 459 914 460 1389 461 461 462 1383 463 463 464 1401 465 934 466 2802 467 467 468 3269 469 7005 470 2335 471 9807 472 3353 473 7185 474 2395 475 10059 476 1437 477 958 478 2874 479 479 480 3409 481 7305 482 2435 483 10227 484 1461 485 974 486 2922 487 487 488 1473 489 982 490 2946 491 491 492 3437 493 7365 494 2455 495 10311 496 1497 497 998 498 2515 499 499 500 1509 501 1006 502 2495 503 503 504 2545 505 10689 506 3563 507 7635 508 3054 509 509 510 1527 511 1018 512 5753 513 17193 514 5731 515 17259 516 6773 517 20397 518 6799 519 20319 520 1569 521 521 522 1563 523 523 524 2605 525 7845 526 2615 527 7815 528 7033 529 41657 530 14066 531 21099 532 11902 533 17853 534 5951 535 35706 536 2705 537 11361 538 3787 539 8115 540 3246 541 541 542 1623 543 1082 544 1641 545 1094 546 3282 547 547 548 3829 549 8205 550 2735 551 11487 552 2785 553 11697 554 3899 555 8355 556 3342 557 557 558 1671 559 1114 560 1689 561 1126 562 3378 563 563 564 3941 565 8445 566 2815 567 11823 568 1713 569 569 570 1707 571 571 572 2845 573 8565 574 2855 575 8535 576 3462 577 577 578 1731 579 1154 580 2885 581 12117 582 4039 583 8655 584 1761 585 1174 586 3522 587 587 588 4109 589 8805 590 2935 591 12327 592 3558 593 593 594 1779 595 1186 596 1797 597 1198 598 3594 599 599 600 3606 601 601 602 1803 603 1202 604 1821 605 1214 606 3642 607 607 608 3065 609 12873 610 4291 611 9195 612 3678 613 613 614 1839 615 1226 616 1857 617 617 618 1851 619 619 620 3085 621 9285 622 3095 623 9255 624 4417 625 9465 626 3155 627 13251 628 1893 629 1262 630 3786 631 631 632 10489 633 24609 634 8203 635 31467 636 6941 637 41646 638 13882 639 20823 640 1929 641 641 642 1923 643 643 644 1941 645 1294 646 3215 647 647 648 3265 649 13713 650 4571 651 9795 652 3918 653 653 654 1959 655 1306 656 1977 657 1318 658 3954 659 659 660 3966 661 661 662 1983 663 1322 664 7249 665 43494 666 14498 667 21747 668 11101 669 21813 670 7271 671 33303 672 3385 673 673 674 2019 675 1346 676 3365 677 677 678 2031 679 1354 680 2049 681 1366 682 4098 683 683 684 4781 685 10245 686 3415 687 14343 688 2073 689 1382 690 4146 691 691 692 4837 693 10365 694 3455 695 14511 696 3505 697 14721 698 4907 699 10515 700 4206 701 701 702 2103 703 1402 704 3545 705 14889 706 4963 707 10635 708 4254 709 709 710 2127 711 1418 712 5033 713 10785 714 3595 715 15099 716 2157 717 1438 718 4314 719 719 720 5089 721 10905 722 3635 723 15267 724 2181 725 1454 726 4362 727 727 728 3665 729 15393 730 5131 731 10995 732 4398 733 733 734 2199 735 1466 736 2217 737 1478 738 3715 739 739 740 2229 741 1486 742 3695 743 743 744 5257 745 11265 746 3755 747 15771 748 2253 749 1502 750 4506 751 751 752 3785 753 15897 754 5299 755 11355 756 4542 757 757 758 2271 759 1514 760 4566 761 761 762 2283 763 1522 764 3805 765 15981 766 5327 767 11415 768 3865 769 769 770 2307 771 1538 772 3845 773 773 774 2319 775 1546 776 10049 777 25377 778 8459 779 30147 780 9997 781 25509 782 8503 783 29991 784 2361 785 1574 786 4722 787 787 788 5509 789 11805 790 3935 791 16527 792 3985 793 16737 794 5579 795 11955 796 4782 797 797 798 2391 799 1594 800 8921 801 26697 802 8899 803 26763 804 10517 805 31629 806 10543 807 31551 808 2433 809 809 810 2427 811 811 812 4045 813 12165 814 4055 815 12135 816 4105 817 12345 818 4115 819 12315 820 2469 821 821 822 2463 823 823 824 2481 825 1654 826 4962 827 827 828 4974 829 829 830 2487 831 1658 832 5873 833 12585 834 4195 835 17619 836 2517 837 1678 838 5034 839 839 840 14569 841 32721 842 10907 843 43707 844 9229 845 44013 846 14671 847 27687 848 4265 849 17913 850 5971 851 12795 852 5118 853 853 854 2559 855 1706 856 2577 857 857 858 2571 859 859 860 2589 861 1726 862 4295 863 863 864 11401 865 45033 866 15011 867 34203 868 16853 869 28941 870 9647 871 50559 872 4385 873 18417 874 6139 875 13155 876 5262 877 877 878 2631 879 1754 880 2649 881 881 882 2643 883 883 884 2661 885 1774 886 4415 887 887 888 9713 889 29073 890 9691 891 29139 892 9757 893 34437 894 11479 895 29271 896 9977 897 35529 898 11843 899 29931 900 10021 901 35373 902 11791 903 30063 904 2721 905 1814 906 4555 907 907 908 2733 909 1822 910 4535 911 911 912 6433 913 13785 914 4595 915 19299 916 2757 917 1838 918 5514 919 919 920 17233 921 35841 922 11947 923 51699 924 10109 925 46461 926 15487 927 30327 928 5574 929 929 930 2787 931 1858 932 4645 933 19509 934 6503 935 13935 936 4705 937 937 938 2811 939 1874 940 4685 941 941 942 2823 943 1882 944 2841 945 1894 946 5682 947 947 948 6629 949 14205 950 4735 951 19887 952 5718 953 953 954 2859 955 1906 956 4765 957 20013 958 6671 959 14295 960 6769 961 14505 962 4835 963 20307 964 2901 965 1934 966 5802 967 967 968 2913 969 1942 970 5826 971 971 972 6797 973 14565 974 4855 975 20391 976 5862 977 977 978 2931 979 1954 980 2949 981 1966 982 5898 983 983 984 6937 985 14865 986 4955 987 20811 988 2973 989 1982 990 5946 991 991 992 4985 993 20937 994 6979 995 14955 996 5982 997 997 998 2991 999 1994 1000 12961