1 0 2 0 3 2 4 10 5 10 6 16 7 22 8 40 9 56 10 48 11 70 12 64 13 66 14 74 15 114 16 130 17 118 18 122 19 138 20 168 21 220 22 174 23 158 24 270 25 242 26 242 27 234 28 212 29 238 30 308 31 284 32 272 33 334 34 296 35 318 36 332 37 424 38 364 39 368 40 416 41 370 42 470 43 524 44 510 45 464 46 474 47 552 48 542 49 480 50 604 51 586 52 554 53 768 54 578 55 752 56 618 57 628 58 880 59 752 60 634 61 702 62 606 63 846 64 820 65 858 66 764 67 928 68 1154 69 726 70 952 71 914 72 788 73 884 74 944 75 1048 76 918 77 878 78 1190 79 974 80 1036 81 998 82 1424 83 1028 84 1182 85 1082 86 1124 87 1232 88 1240 89 1356 90 1322 91 1006 92 1084 93 1246 94 1160 95 1246 96 1166 97 1244 98 1646 99 1356 100 1624 101 1488 102 1342 103 1236 104 1502 105 1600 106 1798 107 1292 108 1442 109 1320 110 1906 111 1564 112 1564 113 1698 114 1498 115 1748 116 1882 117 1540 118 1454 119 1526 120 1586 121 2036 122 2226 123 1700 124 1580 125 1914 126 2166 127 1802 128 1698 129 1974 130 1980 131 1888 132 1874 133 2212 134 2122 135 2178 136 2102 137 1800 138 1968 139 1870 140 1968 141 2246 142 2024 143 2062 144 1960 145 2188 146 1940 147 2234 148 2038 149 2698 150 1986 151 2346 152 2592 153 2400 154 2030 155 2272 156 2692 157 2502 158 2200 159 2776 160 2364 161 2358 162 2634 163 2550 164 2226 165 2440 166 2184 167 2996 168 2762 169 3196 170 2884 171 2220 172 3056 173 2772 174 2776 175 2688 176 2640 177 3032 178 2716 179 2742 180 2882 181 2802 182 2654 183 3168 184 2670 185 2402 186 2544 187 3082 188 3034 189 3152 190 2952 191 3342 192 3066 193 3398 194 3084 195 2656 196 2902 197 3564 198 3208 199 3144 200 2920 201 3020 202 3362 203 3542 204 3988 205 2790 206 3226 207 3380 208 2906 209 3628 210 3676 211 3652 212 3686 213 3492 214 2884 215 3020 216 4066 217 3686 218 3658 219 3102 220 3348 221 4298 222 3544 223 3706 224 3618 225 3292 226 4092 227 3406 228 3228 229 3710 230 3358 231 4058 232 4022 233 4314 234 4030 235 3910 236 3368 237 4034 238 3376 239 3544 240 3648 241 3334 242 4496 243 3736 244 4296 245 3816 246 3450 247 4082 248 3746 249 3832 250 3860 251 4256 252 4372 253 3620 254 4378 255 4386 256 3442 257 4920 258 4010 259 3894 260 4750 261 4248 262 4016 263 4348 264 4720 265 4210 266 4400 267 4270 268 4566 269 4864 270 4070 271 5200 272 4700 273 4714 274 4328 275 5038 276 4608 277 3994 278 4764 279 5420 280 4110 281 4136 282 5414 283 4280 284 5168 285 4708 286 5046 287 5540 288 4668 289 4686 290 4580 291 5118 292 4324 293 4620 294 4814 295 5486 296 4564 297 6190 298 4930 299 4404 300 4844 301 5580 302 4874 303 5372 304 5078 305 5278 306 6348 307 4540 308 5426 309 4584 310 5508 311 4726 312 5070 313 5840 314 5252 315 4904 316 6004 317 4742 318 5038 319 6186 320 6188 321 5710 322 5828 323 5576 324 6868 325 5310 326 6732 327 6578 328 5458 329 4988 330 5532 331 6744 332 5550 333 5640 334 5090 335 6462 336 5054 337 7110 338 5460 339 7374 340 6040 341 5994 342 6220 343 5608 344 7054 345 6012 346 5418 347 7742 348 6170 349 6138 350 5848 351 6508 352 7366 353 7474 354 5960 355 6244 356 6194 357 5434 358 5896 359 5964 360 5654 361 7112 362 7166 363 5462 364 5524 365 6684 366 6776 367 5846 368 6614 369 9182 370 6528 371 6950 372 5618 373 6566 374 7526 375 7284 376 5644 377 7406 378 8224 379 6660 380 7280 381 6914 382 7314 383 7420 384 6548 385 6514 386 6302 387 7252 388 7080 389 6910 390 6310 391 7892 392 6284 393 6022 394 7448 395 6806 396 7772 397 7066 398 7032 399 8224 400 7356 401 7448 402 6834 403 6910 404 6824 405 6638 406 8302 407 7324 408 8506 409 6850 410 6456 411 8002 412 6734 413 7098 414 7896 415 9168 416 8548 417 6592 418 7560 419 7232 420 6606 421 6996 422 8210 423 8342 424 6856 425 8498 426 6876 427 6616 428 7900 429 8632 430 6900 431 9980 432 8118 433 7546 434 6840 435 8664 436 8490 437 8254 438 9068 439 8150 440 8322 441 7170 442 7858 443 9062 444 7164 445 11150 446 8162 447 8178 448 7158 449 10036 450 9390 451 8330 452 8310 453 7076 454 7712 455 8952 456 8900 457 8464 458 8114 459 8636 460 8432 461 8382 462 8772 463 7404 464 9818 465 8406 466 9950 467 9606 468 7344 469 8670 470 9442 471 8644 472 8024 473 8170 474 11688 475 8084 476 9104 477 9220 478 9626 479 7990 480 8066 481 10276 482 8370 483 10476 484 8938 485 8574 486 7702 487 9524 488 8498 489 8778 490 9972 491 9232 492 7702 493 11226 494 8496 495 8106 496 10872 497 9012 498 8876 499 9082 500 11124 501 8996 502 9450 503 8530 504 9218 505 10818 506 9116 507 8324 508 10374 509 10338 510 9056 511 8674 512 9082 513 10810 514 8766 515 10106 516 12464 517 9822 518 10438 519 9182 520 9858 521 9788 522 10634 523 10150 524 9032 525 10420 526 8396 527 10764 528 9734 529 8348 530 9550 531 10484 532 9338 533 9690 534 10588 535 10578 536 8696 537 10818 538 10080 539 12128 540 11018 541 10186 542 9776 543 9746 544 8706 545 9436 546 10780 547 10586 548 8958 549 10064 550 9300 551 11446 552 11158 553 9116 554 9828 555 9792 556 12190 557 10748 558 11242 559 11890 560 12132 561 9818 562 9060 563 9866 564 11676 565 10300 566 11192 567 9376 568 11990 569 9792 570 9258 571 11488 572 9944 573 12456 574 14044 575 14424 576 10294 577 10630 578 10664 579 10688 580 13024 581 12602 582 11428 583 10160 584 9448 585 12532 586 11342 587 11872 588 9430 589 10554 590 11980 591 12030 592 10654 593 11382 594 10178 595 13338 596 10916 597 10304 598 10914 599 11090 600 11128 601 11696 602 11552 603 13868 604 12568 605 10776 606 10786 607 10378 608 13398 609 11964 610 10582 611 11392 612 13654 613 10706 614 11606 615 11530 616 10168 617 12176 618 15322 619 11736 620 10720 621 13688 622 12218 623 12040 624 15470 625 11390 626 11600 627 10664 628 12060 629 13084 630 12806 631 13056 632 11476 633 10482 634 12338 635 10640 636 14056 637 12056 638 12730 639 14290 640 12396 641 12990 642 12146 643 10664 644 14424 645 11652 646 10856 647 15106 648 12950 649 12766 650 15158 651 14680 652 12040 653 12010 654 12374 655 13770 656 13146 657 11188 658 12300 659 13430 660 11898 661 11694 662 15462 663 14260 664 11584 665 14610 666 11998 667 13198 668 15084 669 13702 670 11740 671 12270 672 13652 673 13096 674 13628 675 11800 676 12682 677 12876 678 14024 679 13568 680 11462 681 11260 682 15922 683 13060 684 15724 685 13052 686 12430 687 14374 688 14550 689 13162 690 13170 691 12236 692 14180 693 16012 694 13686 695 13066 696 14884 697 13992 698 13498 699 12838 700 14156 701 17500 702 13496 703 12628 704 12512 705 13370 706 13446 707 14446 708 13530 709 14178 710 11992 711 13364 712 12178 713 14218 714 14880 715 13142 716 14826 717 14794 718 14968 719 15930 720 13486 721 15172 722 13406 723 13300 724 14286 725 12584 726 15058 727 14636 728 12374 729 12678 730 19116 731 14440 732 14774 733 14526 734 14672 735 16084 736 13924 737 16692 738 14966 739 14122 740 12730 741 17250 742 14228 743 13704 744 15282 745 14730 746 14098 747 13692 748 14586 749 16882 750 13392 751 17016 752 14072 753 13442 754 15872 755 15936 756 15816 757 15186 758 14866 759 14100 760 15928 761 15724 762 13196 763 14030 764 16724 765 14764 766 15976 767 13102 768 15196 769 17976 770 16526 771 14880 772 13792 773 16326 774 13220 775 19220 776 14906 777 14322 778 16766 779 13396 780 13292 781 17170 782 17098 783 13110 784 17776 785 14802 786 14510 787 16050 788 16148 789 13908 790 15596 791 15788 792 17762 793 15458 794 14960 795 17588 796 15962 797 15030 798 19658 799 14984 800 17418 801 14314 802 17114 803 17116 804 14418 805 14912 806 15584 807 14470 808 18342 809 18368 810 16296 811 17420 812 16634 813 16378 814 14320 815 15038 816 18470 817 17124 818 14838 819 14364 820 20208 821 15468 822 15110 823 14088 824 16794 825 20034 826 17314 827 15752 828 15556 829 19434 830 15978 831 18264 832 16274 833 15270 834 17520 835 20034 836 19080 837 17866 838 17642 839 19926 840 15922 841 21466 842 16826 843 17534 844 20532 845 16526 846 16348 847 22450 848 14820 849 15928 850 19144 851 18564 852 18760 853 14784 854 17302 855 16458 856 19054 857 15596 858 14998 859 21358 860 18540 861 19020 862 18520 863 18476 864 17660 865 16752 866 19150 867 15242 868 19186 869 16380 870 19190 871 18232 872 15130 873 19496 874 17972 875 19192 876 15762 877 17846 878 15302 879 18178 880 19458 881 22556 882 16976 883 15804 884 16760 885 21194 886 18366 887 15436 888 17084 889 16976 890 17978 891 16142 892 19114 893 17664 894 21872 895 19218 896 17440 897 16978 898 15920 899 19612 900 21528 901 20390 902 16710 903 16378 904 17696 905 20542 906 16542 907 21564 908 19482 909 15930 910 16206 911 16754 912 20248 913 18136 914 21324 915 19498 916 17972 917 22268 918 16230 919 18094 920 18144 921 18776 922 19202 923 18788 924 17936 925 20012 926 18764 927 16184 928 18468 929 16966 930 21120 931 17370 932 22572 933 22640 934 17808 935 20186 936 18460 937 22048 938 20950 939 23716 940 24276 941 21298 942 18174 943 18234 944 19354 945 19808 946 21556 947 21658 948 17298 949 23004 950 17358 951 20340 952 17908 953 16818 954 18234 955 21282 956 22220 957 18500 958 21152 959 17074 960 27710 961 20846 962 18260 963 17728 964 19032 965 22586 966 20230 967 17034 968 23144 969 20176 970 17096 971 18976 972 21494 973 20228 974 24512 975 23904 976 18406 977 19292 978 17618 979 21018 980 22176 981 17462 982 24684 983 22570 984 20082 985 20560 986 22086 987 19052 988 19120 989 17770 990 18804 991 23966 992 20164 993 21068 994 22092 995 20058 996 20952 997 19034 998 20452 999 17488 1000 18076