1 1 2 0 3 2 4 0 5 6 6 0 7 10 8 0 9 4 10 0 11 18 12 0 13 22 14 0 15 12 16 0 17 30 18 0 19 34 20 0 21 20 22 0 23 42 24 0 25 36 26 0 27 8 28 0 29 54 30 0 31 58 32 0 33 36 34 0 35 60 36 0 37 70 38 0 39 44 40 0 41 78 42 0 43 82 44 0 45 24 46 0 47 90 48 0 49 100 50 0 51 60 52 0 53 102 54 0 55 108 56 0 57 68 58 0 59 114 60 0 61 118 62 0 63 40 64 0 65 132 66 0 67 130 68 0 69 84 70 0 71 138 72 0 73 142 74 0 75 72 76 0 77 180 78 0 79 154 80 0 81 16 82 0 83 162 84 0 85 180 86 0 87 108 88 0 89 174 90 0 91 220 92 0 93 116 94 0 95 204 96 0 97 190 98 0 99 72 100 0 101 198 102 0 103 202 104 0 105 120 106 0 107 210 108 0 109 214 110 0 111 140 112 0 113 222 114 0 115 252 116 0 117 88 118 0 119 300 120 0 121 324 122 0 123 156 124 0 125 216 126 0 127 250 128 0 129 164 130 0 131 258 132 0 133 340 134 0 135 48 136 0 137 270 138 0 139 274 140 0 141 180 142 0 143 396 144 0 145 324 146 0 147 200 148 0 149 294 150 0 151 298 152 0 153 120 154 0 155 348 156 0 157 310 158 0 159 204 160 0 161 420 162 0 163 322 164 0 165 216 166 0 167 330 168 0 169 484 170 0 171 136 172 0 173 342 174 0 175 360 176 0 177 228 178 0 179 354 180 0 181 358 182 0 183 236 184 0 185 420 186 0 187 540 188 0 189 80 190 0 191 378 192 0 193 382 194 0 195 264 196 0 197 390 198 0 199 394 200 0 201 260 202 0 203 540 204 0 205 468 206 0 207 168 208 0 209 612 210 0 211 418 212 0 213 276 214 0 215 492 216 0 217 580 218 0 219 284 220 0 221 660 222 0 223 442 224 0 225 144 226 0 227 450 228 0 229 454 230 0 231 360 232 0 233 462 234 0 235 540 236 0 237 308 238 0 239 474 240 0 241 478 242 0 243 32 244 0 245 600 246 0 247 748 248 0 249 324 250 0 251 498 252 0 253 756 254 0 255 360 256 0 257 510 258 0 259 700 260 0 261 216 262 0 263 522 264 0 265 612 266 0 267 348 268 0 269 534 270 0 271 538 272 0 273 440 274 0 275 648 276 0 277 550 278 0 279 232 280 0 281 558 282 0 283 562 284 0 285 408 286 0 287 780 288 0 289 900 290 0 291 380 292 0 293 582 294 0 295 684 296 0 297 144 298 0 299 924 300 0 301 820 302 0 303 396 304 0 305 708 306 0 307 610 308 0 309 404 310 0 311 618 312 0 313 622 314 0 315 240 316 0 317 630 318 0 319 972 320 0 321 420 322 0 323 1020 324 0 325 792 326 0 327 428 328 0 329 900 330 0 331 658 332 0 333 280 334 0 335 780 336 0 337 670 338 0 339 444 340 0 341 1044 342 0 343 1000 344 0 345 504 346 0 347 690 348 0 349 694 350 0 351 176 352 0 353 702 354 0 355 828 356 0 357 600 358 0 359 714 360 0 361 1156 362 0 363 648 364 0 365 852 366 0 367 730 368 0 369 312 370 0 371 1020 372 0 373 742 374 0 375 432 376 0 377 1188 378 0 379 754 380 0 381 500 382 0 383 762 384 0 385 1080 386 0 387 328 388 0 389 774 390 0 391 1260 392 0 393 516 394 0 395 924 396 0 397 790 398 0 399 680 400 0 401 798 402 0 403 1276 404 0 405 96 406 0 407 1260 408 0 409 814 410 0 411 540 412 0 413 1140 414 0 415 972 416 0 417 548 418 0 419 834 420 0 421 838 422 0 423 360 424 0 425 1080 426 0 427 1180 428 0 429 792 430 0 431 858 432 0 433 862 434 0 435 648 436 0 437 1428 438 0 439 874 440 0 441 400 442 0 443 882 444 0 445 1044 446 0 447 588 448 0 449 894 450 0 451 1404 452 0 453 596 454 0 455 1320 456 0 457 910 458 0 459 240 460 0 461 918 462 0 463 922 464 0 465 696 466 0 467 930 468 0 469 1300 470 0 471 620 472 0 473 1476 474 0 475 1224 476 0 477 408 478 0 479 954 480 0 481 1540 482 0 483 840 484 0 485 1140 486 0 487 970 488 0 489 644 490 0 491 978 492 0 493 1620 494 0 495 432 496 0 497 1380 498 0 499 994 500 0 501 660 502 0 503 1002 504 0 505 1188 506 0 507 968 508 0 509 1014 510 0 511 1420 512 0 513 272 514 0 515 1212 516 0 517 1620 518 0 519 684 520 0 521 1038 522 0 523 1042 524 0 525 720 526 0 527 1740 528 0 529 1764 530 0 531 456 532 0 533 1716 534 0 535 1260 536 0 537 708 538 0 539 1800 540 0 541 1078 542 0 543 716 544 0 545 1284 546 0 547 1090 548 0 549 472 550 0 551 1836 552 0 553 1540 554 0 555 840 556 0 557 1110 558 0 559 1804 560 0 561 1080 562 0 563 1122 564 0 565 1332 566 0 567 160 568 0 569 1134 570 0 571 1138 572 0 573 756 574 0 575 1512 576 0 577 1150 578 0 579 764 580 0 581 1620 582 0 583 1836 584 0 585 528 586 0 587 1170 588 0 589 1972 590 0 591 780 592 0 593 1182 594 0 595 1800 596 0 597 788 598 0 599 1194 600 0 601 1198 602 0 603 520 604 0 605 1944 606 0 607 1210 608 0 609 1080 610 0 611 1980 612 0 613 1222 614 0 615 936 616 0 617 1230 618 0 619 1234 620 0 621 336 622 0 623 1740 624 0 625 1296 626 0 627 1224 628 0 629 2100 630 0 631 1258 632 0 633 836 634 0 635 1500 636 0 637 2200 638 0 639 552 640 0 641 1278 642 0 643 1282 644 0 645 984 646 0 647 1290 648 0 649 2052 650 0 651 1160 652 0 653 1302 654 0 655 1548 656 0 657 568 658 0 659 1314 660 0 661 1318 662 0 663 1320 664 0 665 2040 666 0 667 2268 668 0 669 884 670 0 671 2124 672 0 673 1342 674 0 675 288 676 0 677 1350 678 0 679 1900 680 0 681 900 682 0 683 1362 684 0 685 1620 686 0 687 908 688 0 689 2244 690 0 691 1378 692 0 693 720 694 0 695 1644 696 0 697 2340 698 0 699 924 700 0 701 1398 702 0 703 2380 704 0 705 1080 706 0 707 1980 708 0 709 1414 710 0 711 616 712 0 713 2436 714 0 715 2376 716 0 717 948 718 0 719 1434 720 0 721 2020 722 0 723 956 724 0 725 1944 726 0 727 1450 728 0 729 64 730 0 731 2460 732 0 733 1462 734 0 735 1200 736 0 737 2340 738 0 739 1474 740 0 741 1496 742 0 743 1482 744 0 745 1764 746 0 747 648 748 0 749 2100 750 0 751 1498 752 0 753 996 754 0 755 1788 756 0 757 1510 758 0 759 1512 760 0 761 1518 762 0 763 2140 764 0 765 720 766 0 767 2508 768 0 769 1534 770 0 771 1020 772 0 773 1542 774 0 775 2088 776 0 777 1400 778 0 779 2652 780 0 781 2484 782 0 783 432 784 0 785 1860 786 0 787 1570 788 0 789 1044 790 0 791 2220 792 0 793 2596 794 0 795 1224 796 0 797 1590 798 0 799 2700 800 0 801 696 802 0 803 2556 804 0 805 2520 806 0 807 1068 808 0 809 1614 810 0 811 1618 812 0 813 1076 814 0 815 1932 816 0 817 2788 818 0 819 880 820 0 821 1638 822 0 823 1642 824 0 825 1296 826 0 827 1650 828 0 829 1654 830 0 831 1100 832 0 833 3000 834 0 835 1980 836 0 837 464 838 0 839 1674 840 0 841 2916 842 0 843 1116 844 0 845 2904 846 0 847 3240 848 0 849 1124 850 0 851 2940 852 0 853 1702 854 0 855 816 856 0 857 1710 858 0 859 1714 860 0 861 1560 862 0 863 1722 864 0 865 2052 866 0 867 1800 868 0 869 2772 870 0 871 2860 872 0 873 760 874 0 875 2160 876 0 877 1750 878 0 879 1164 880 0 881 1758 882 0 883 1762 884 0 885 1368 886 0 887 1770 888 0 889 2500 890 0 891 288 892 0 893 3060 894 0 895 2124 896 0 897 1848 898 0 899 3132 900 0 901 3060 902 0 903 1640 904 0 905 2148 906 0 907 1810 908 0 909 792 910 0 911 1818 912 0 913 2916 914 0 915 1416 916 0 917 2580 918 0 919 1834 920 0 921 1220 922 0 923 3036 924 0 925 2520 926 0 927 808 928 0 929 1854 930 0 931 3400 932 0 933 1236 934 0 935 3240 936 0 937 1870 938 0 939 1244 940 0 941 1878 942 0 943 3276 944 0 945 480 946 0 947 1890 948 0 949 3124 950 0 951 1260 952 0 953 1902 954 0 955 2268 956 0 957 1944 958 0 959 2700 960 0 961 3364 962 0 963 840 964 0 965 2292 966 0 967 1930 968 0 969 2040 970 0 971 1938 972 0 973 2740 974 0 975 1584 976 0 977 1950 978 0 979 3132 980 0 981 856 982 0 983 1962 984 0 985 2340 986 0 987 1800 988 0 989 3444 990 0 991 1978 992 0 993 1316 994 0 995 2364 996 0 997 1990 998 0 999 560 1000 0