0 1 1 2 2 4 3 6 4 10 5 14 6 20 7 24 8 30 9 36 10 44 11 48 12 60 13 60 14 62 15 72 16 82 17 88 18 96 19 112 20 120 21 120 22 136 23 148 24 164 25 152 26 154 27 148 28 162 29 176 30 190 31 196 32 210 33 216 34 224 35 228 36 248 37 272 38 284 39 296 40 300 41 296 42 320 43 332 44 356 45 356 46 376 47 400 48 416 49 380 50 382 51 376 52 382 53 356 54 374 55 392 56 410 57 432 58 458 59 464 60 486 61 476 62 498 63 500 64 522 65 528 66 540 67 548 68 568 69 560 70 592 71 592 72 620 73 660 74 688 75 688 76 722 77 724 78 740 79 724 80 724 81 716 82 748 83 788 84 824 85 816 86 856 87 868 88 880 89 868 90 912 91 908 92 960 93 976 94 1008 95 1000 96 1016 97 940 98 942 99 936 100 958 101 924 102 946 103 936 104 922 105 880 106 926 107 908 108 960 109 956 110 986 111 984 112 1010 113 1044 114 1082 115 1128 116 1170 117 1140 118 1182 119 1192 120 1198 121 1176 122 1234 123 1224 124 1268 125 1232 126 1278 127 1240 128 1278 129 1292 130 1316 131 1312 132 1356 133 1340 134 1380 135 1392 136 1400 137 1392 138 1468 139 1456 140 1514 141 1444 142 1492 143 1480 144 1524 145 1588 146 1632 147 1692 148 1744 149 1696 150 1762 151 1756 152 1780 153 1780 154 1848 155 1824 156 1868 157 1800 158 1840 159 1720 160 1716 161 1724 162 1784 163 1808 164 1892 165 1928 166 1996 167 2012 168 2028 169 2012 170 2112 171 2092 172 2180 173 2116 174 2156 175 2120 176 2120 177 2096 178 2164 179 2248 180 2316 181 2232 182 2324 183 2336 184 2380 185 2404 186 2508 187 2476 188 2552 189 2468 190 2532 191 2420 192 2444 193 2312 194 2322 195 2300 196 2358 197 2304 198 2366 199 2336 200 2330 201 2284 202 2378 203 2320 204 2398 205 2300 206 2318 207 2220 208 2190 209 2128 210 2194 211 2300 212 2354 213 2244 214 2340 215 2352 216 2382 217 2368 218 2478 219 2420 220 2500 221 2432 222 2506 223 2404 224 2442 225 2520 226 2598 227 2628 228 2742 229 2776 230 2866 231 2860 232 2866 233 2816 234 2946 235 2892 236 3006 237 2920 238 2966 239 2880 240 2874 241 2844 242 2938 243 3048 244 3134 245 3012 246 3108 247 3120 248 3126 249 3072 250 3222 251 3164 252 3244 253 3060 254 3154 255 3036 256 3114 257 3156 258 3212 259 3228 260 3320 261 3240 262 3344 263 3296 264 3316 265 3308 266 3452 267 3372 268 3510 269 3416 270 3472 271 3364 272 3372 273 3364 274 3472 275 3644 276 3744 277 3604 278 3734 279 3732 280 3720 281 3588 282 3760 283 3672 284 3788 285 3660 286 3776 287 3624 288 3692 289 3836 290 3944 291 3960 292 4124 293 4164 294 4284 295 4272 296 4276 297 4212 298 4414 299 4332 300 4490 301 4308 302 4392 303 4264 304 4286 305 4292 306 4412 307 4560 308 4680 309 4500 310 4624 311 4596 312 4588 313 4496 314 4684 315 4596 316 4652 317 4284 318 4368 319 4076 320 4088 321 4172 322 4300 323 4364 324 4516 325 4460 326 4628 327 4584 328 4664 329 4748 330 4956 331 4880 332 5076 333 4932 334 5020 335 4876 336 4884 337 4860 338 5008 339 5240 340 5384 341 5188 342 5384 343 5340 344 5352 345 5228 346 5436 347 5304 348 5448 349 5264 350 5372 351 5056 352 5044 353 5068 354 5220 355 5260 356 5484 357 5536 358 5696 359 5680 360 5668 361 5540 362 5812 363 5700 364 5928 365 5720 366 5840 367 5708 368 5760 369 5804 370 5976 371 6200 372 6364 373 6112 374 6300 375 6272 376 6272 377 6148 378 6416 379 6288 380 6408 381 6008 382 6152 383 5804 384 5868 385 5676 386 5722 387 5680 388 5822 389 5672 390 5830 391 5748 392 5758 393 5708 394 5950 395 5816 396 6012 397 5748 398 5826 399 5596 400 5578 401 5512 402 5654 403 5920 404 6050 405 5776 406 5978 407 5892 408 5882 409 5712 410 5922 411 5748 412 5848 413 5564 414 5662 415 5208 416 5158 417 5144 418 5302 419 5320 420 5562 421 5668 422 5818 423 5776 424 5738 425 5572 426 5848 427 5744 428 5976 429 5756 430 5858 431 5728 432 5748 433 5720 434 5894 435 6148 436 6290 437 5976 438 6168 439 6144 440 6158 441 6064 442 6342 443 6220 444 6348 445 5956 446 6110 447 5800 448 5882 449 6096 450 6274 451 6352 452 6562 453 6484 454 6718 455 6660 456 6762 457 6860 458 7162 459 7024 460 7280 461 7016 462 7122 463 6892 464 6878 465 6804 466 7002 467 7324 468 7502 469 7184 470 7450 471 7372 472 7390 473 7236 474 7518 475 7324 476 7492 477 7172 478 7318 479 6848 480 6834 481 6876 482 7082 483 7160 484 7466 485 7532 486 7754 487 7664 488 7638 489 7444 490 7772 491 7616 492 7908 493 7664 494 7778 495 7512 496 7500 497 7428 498 7662 499 8004 500 8198 501 7832 502 8064 503 8012 504 7946 505 7652 506 8018 507 7824 508 7996 509 7520 510 7742 511 7384 512 7554 513 7692 514 7836 515 7848 516 8084 517 7956 518 8184 519 8120 520 8136 521 8052 522 8420 523 8228 524 8506 525 8092 526 8224 527 7956 528 7984 529 7980 530 8192 531 8584 532 8776 533 8376 534 8690 535 8612 536 8644 537 8472 538 8808 539 8592 540 8776 541 8404 542 8604 543 8008 544 8016 545 8116 546 8364 547 8412 548 8796 549 8976 550 9232 551 9160 552 9132 553 8916 554 9322 555 9168 556 9506 557 9156 558 9268 559 8960 560 8886 561 8676 562 8948 563 9336 564 9552 565 9068 566 9352 567 9328 568 9328 569 9144 570 9576 571 9372 572 9572 573 8968 574 9204 575 8776 576 8924 577 9292 578 9552 579 9668 580 9964 581 9792 582 10140 583 10016 584 10160 585 10300 586 10748 587 10496 588 10876 589 10488 590 10640 591 10272 592 10260 593 10176 594 10478 595 10980 596 11238 597 10760 598 11146 599 11048 600 11030 601 10708 602 11156 603 10848 604 11104 605 10596 606 10834 607 10208 608 10236 609 10368 610 10652 611 10748 612 11192 613 11272 614 11592 615 11440 616 11404 617 11128 618 11600 619 11360 620 11748 621 11324 622 11488 623 10996 624 10964 625 10852 626 11164 627 11624 628 11888 629 11396 630 11676 631 11524 632 11332 633 10760 634 11240 635 10904 636 11032 637 10140 638 10348 639 9688 640 9776 641 10092 642 10384 643 10500 644 10860 645 10744 646 11076 647 11040 648 11112 649 11084 650 11616 651 11380 652 11784 653 11236 654 11472 655 11172 656 11300 657 11448 658 11760 659 12288 660 12592 661 12100 662 12544 663 12444 664 12480 665 12216 666 12704 667 12404 668 12680 669 12152 670 12428 671 11600 672 11600 673 11720 674 12068 675 12124 676 12660 677 12884 678 13240 679 13192 680 13160 681 12868 682 13472 683 13248 684 13704 685 13100 686 13292 687 12860 688 12812 689 12620 690 12972 691 13472 692 13772 693 13112 694 13500 695 13396 696 13392 697 13148 698 13704 699 13384 700 13572 701 12580 702 12820 703 11984 704 12020 705 12268 706 12620 707 12784 708 13188 709 12996 710 13464 711 13320 712 13512 713 13684 714 14276 715 13952 716 14456 717 13940 718 14124 719 13632 720 13576 721 13388 722 13788 723 14464 724 14804 725 14156 726 14684 727 14572 728 14580 729 14200 730 14800 731 14404 732 14772 733 14180 734 14524 735 13712 736 13784 737 14020 738 14420 739 14540 740 15156 741 15308 742 15740 743 15572 744 15516 745 15128 746 15792 747 15476 748 16020 749 15428 750 15652 751 15052 752 15012 753 14852 754 15292 755 15924 756 16292 757 15572 758 15992 759 15840 760 15672 761 15060 762 15744 763 15328 764 15564 765 14420 766 14764 767 13916 768 14112 769 13900 770 14058 771 14004 772 14366 773 14012 774 14398 775 14208 776 14222 777 14072 778 14686 779 14336 780 14814 781 14136 782 14350 783 13804 784 13818 785 13760 786 14118 787 14796 788 15118 789 14460 790 14964 791 14788 792 14750 793 14288 794 14854 795 14440 796 14708 797 13988 798 14286 799 13240 800 13202 801 13288 802 13658 803 13680 804 14286 805 14576 806 14946 807 14836 808 14750 809 14344 810 15006 811 14740 812 15210 813 14484 814 14678 815 14116 816 14034 817 13776 818 14146 819 14688 820 14978 821 14224 822 14592 823 14424 824 14338 825 13964 826 14554 827 14184 828 14284 829 12984 830 13194 831 12236 832 12234 833 12440 834 12794 835 12996 836 13390 837 13144 838 13638 839 13480 840 13722 841 13984 842 14562 843 14260 844 14744 845 14196 846 14370 847 13796 848 13702 849 13460 850 13860 851 14560 852 14908 853 14284 854 14828 855 14684 856 14684 857 14268 858 14846 859 14440 860 14804 861 14248 862 14568 863 13692 864 13698 865 13812 866 14210 867 14328 868 14966 869 15180 870 15586 871 15416 872 15302 873 14796 874 15452 875 15160 876 15700 877 15116 878 15350 879 14780 880 14768 881 14652 882 15098 883 15748 884 16118 885 15404 886 15832 887 15688 888 15526 889 14916 890 15602 891 15200 892 15464 893 14392 894 14750 895 13952 896 14170 897 14756 898 15178 899 15340 900 15858 901 15668 902 16150 903 16024 904 16126 905 16104 906 16862 907 16516 908 17106 909 16336 910 16666 911 16204 912 16370 913 16544 914 16994 915 17796 916 18210 917 17452 918 18080 919 17864 920 17862 921 17392 922 18074 923 17608 924 17976 925 17192 926 17558 927 16336 928 16298 929 16408 930 16886 931 16956 932 17706 933 18020 934 18494 935 18388 936 18302 937 17824 938 18658 939 18344 940 18958 941 18096 942 18366 943 17736 944 17686 945 17452 946 17930 947 18636 948 19026 949 18116 950 18628 951 18444 952 18378 953 17940 954 18710 955 18252 956 18472 957 17036 958 17362 959 16208 960 16266 961 16612 962 17082 963 17304 964 17862 965 17652 966 18278 967 18156 968 18418 969 18632 970 19438 971 19040 972 19664 973 18824 974 19074 975 18352 976 18254 977 17964 978 18460 979 19320 980 19768 981 18928 982 19624 983 19408 984 19444 985 19008 986 19746 987 19244 988 19640 989 18748 990 19152 991 17832 992 17802 993 17924 994 18454 995 18616 996 19450 997 19760 998 20306 999 20056 1000 19942