0 1 1 2 2 5 3 7 4 9 5 11 6 10 7 15 8 14 9 19 10 21 11 21 12 28 13 24 14 29 15 26 16 26 17 35 18 37 19 39 20 41 21 34 22 43 23 47 24 49 25 56 26 42 27 55 28 57 29 50 30 56 31 50 32 60 33 74 34 69 35 76 36 52 37 70 38 84 39 79 40 81 41 66 42 85 43 74 44 98 45 91 46 74 47 88 48 97 49 99 50 86 51 84 52 105 53 107 54 109 55 122 56 90 57 98 58 124 59 119 60 121 61 105 62 125 63 127 64 112 65 131 66 112 67 135 68 130 69 139 70 132 71 100 72 152 73 140 74 149 75 151 76 122 77 183 78 134 79 159 80 161 81 128 82 165 83 167 84 169 85 146 86 147 87 175 88 194 89 168 90 196 91 146 92 158 93 187 94 189 95 182 96 154 97 195 98 184 99 180 100 201 101 162 102 205 103 224 104 220 105 211 106 148 107 215 108 204 109 228 110 242 111 189 112 225 113 194 114 220 115 216 116 196 117 235 118 237 119 248 120 215 121 208 122 245 123 247 124 238 125 251 126 202 127 216 128 257 129 280 130 250 131 210 132 273 133 267 134 230 135 271 136 231 137 275 138 277 139 279 140 281 141 196 142 308 143 314 144 289 145 291 146 228 147 295 148 254 149 280 150 316 151 242 152 305 153 294 154 338 155 280 156 250 157 315 158 317 159 308 160 321 161 260 162 278 163 327 164 329 165 343 166 256 167 335 168 364 169 301 170 341 171 274 172 345 173 364 174 338 175 351 176 266 177 355 178 357 179 370 180 372 181 308 182 350 183 304 184 348 185 371 186 315 187 410 188 377 189 379 190 326 191 306 192 370 193 387 194 420 195 391 196 320 197 338 198 434 199 399 200 376 201 322 202 392 203 384 204 350 205 411 206 330 207 448 208 417 209 458 210 421 211 294 212 425 213 440 214 429 215 431 216 346 217 408 218 387 219 460 220 532 221 354 222 420 223 430 224 449 225 386 226 362 227 442 228 457 229 459 230 461 231 400 232 398 233 504 234 440 235 471 236 399 237 460 238 490 239 410 240 462 241 372 242 553 243 487 244 489 245 476 246 366 247 495 248 484 249 499 250 501 251 384 252 518 253 468 254 490 255 511 256 410 257 532 258 517 259 560 260 432 261 441 262 525 263 527 264 578 265 556 266 426 267 473 268 504 269 518 270 541 271 434 272 588 273 547 274 470 275 602 276 442 277 555 278 540 279 528 280 546 281 388 282 565 283 567 284 569 285 560 286 521 287 575 288 504 289 579 290 581 291 466 292 585 293 587 294 608 295 506 296 474 297 665 298 588 299 599 300 601 301 482 302 496 303 607 304 609 305 611 306 490 307 632 308 674 309 530 310 621 311 588 312 625 313 627 314 629 315 616 316 430 317 600 318 637 319 640 320 641 321 514 322 660 323 554 324 700 325 666 326 522 327 630 328 657 329 659 330 612 331 532 332 650 333 650 334 700 335 686 336 504 337 616 338 677 339 679 340 681 341 592 342 685 343 687 344 590 345 691 346 554 347 670 348 697 349 699 350 756 351 484 352 770 353 664 354 728 355 672 356 560 357 748 358 614 359 719 360 700 361 609 362 725 363 868 364 729 365 645 366 586 367 735 368 760 369 739 370 696 371 594 372 638 373 747 374 756 375 751 376 644 377 755 378 730 379 650 380 796 381 610 382 748 383 767 384 769 385 813 386 546 387 728 388 777 389 840 390 781 391 626 392 785 393 648 394 789 395 791 396 688 397 795 398 814 399 799 400 686 401 640 402 868 403 844 404 760 405 836 406 650 407 756 408 817 409 790 410 821 411 676 412 780 413 827 414 700 415 915 416 666 417 812 418 931 419 839 420 841 421 546 422 845 423 847 424 868 425 851 426 704 427 855 428 784 429 938 430 861 431 660 432 882 433 850 434 869 435 746 436 735 437 875 438 824 439 858 440 931 441 756 442 760 443 854 444 889 445 891 446 714 447 895 448 920 449 792 450 852 451 784 452 905 453 907 454 980 455 856 456 628 457 915 458 917 459 919 460 896 461 777 462 1010 463 817 464 948 465 931 466 746 467 1008 468 937 469 888 470 806 471 740 472 896 473 1034 474 970 475 951 476 762 477 818 478 957 479 988 480 1036 481 770 482 965 483 940 484 900 485 992 486 819 487 975 488 924 489 920 490 962 491 676 492 962 493 1064 494 989 495 1152 496 794 497 995 498 854 499 999 500 1001 501 784 502 970 503 980 504 1009 505 866 506 896 507 960 508 1017 509 1019 510 1021 511 861 512 903 513 1027 514 1029 515 1012 516 836 517 1130 518 1084 519 952 520 1041 521 834 522 1045 523 984 524 1020 525 1051 526 686 527 1055 528 1154 529 1078 530 1022 531 850 532 1148 533 900 534 1050 535 1092 536 884 537 1075 538 1077 539 1197 540 880 541 896 542 1112 543 1087 544 1110 545 1092 546 868 547 938 548 1097 549 1099 550 1202 551 882 552 1105 553 1140 554 950 555 1111 556 890 557 1048 558 1204 559 1078 560 1121 561 903 562 1125 563 1127 564 1080 565 1100 566 906 567 1135 568 974 569 1118 570 1141 571 980 572 1250 573 1147 574 1080 575 986 576 922 577 1155 578 1157 579 1159 580 1161 581 930 582 998 583 1188 584 1281 585 1171 586 987 587 1228 588 1134 589 1008 590 1216 591 896 592 1210 593 1187 594 1298 595 1150 596 820 597 1288 598 1170 599 1199 600 1201 601 962 602 1140 603 1034 604 1188 605 1322 606 960 607 1240 608 1144 609 1219 610 1204 611 1029 612 1225 613 1227 614 1229 615 1231 616 1072 617 1036 618 1237 619 1239 620 1241 621 948 622 1245 623 1344 624 1070 625 1176 626 980 627 1407 628 1257 629 1259 630 1261 631 868 632 1232 633 1324 634 1269 635 1250 636 1176 637 1275 638 1188 639 1258 640 1212 641 1026 642 1208 643 1287 644 1289 645 1106 646 1008 647 1260 648 1274 649 1540 650 1276 651 1040 652 1118 653 1307 654 1288 655 1311 656 1088 657 1270 658 1317 659 1032 660 1463 661 1092 662 1428 663 1327 664 1368 665 1331 666 916 667 1358 668 1364 669 1339 670 1341 671 1168 672 1345 673 1154 674 1349 675 1372 676 1024 677 1380 678 1284 679 1420 680 1166 681 1090 682 1490 683 1400 684 1369 685 1371 686 1155 687 1178 688 1400 689 1379 690 1406 691 1106 692 1385 693 1408 694 1190 695 1391 696 1114 697 1320 698 1397 699 1399 700 1401 701 1064 702 1468 703 1407 704 1456 705 1411 706 1130 707 1415 708 1247 709 1419 710 1365 711 1197 712 1425 713 1427 714 1540 715 1332 716 1092 717 1408 718 1400 719 1390 720 1441 721 1154 722 1238 723 1470 724 1449 725 1516 726 1264 727 1456 728 1457 729 1240 730 1496 731 1170 732 1465 733 1414 734 1469 735 1392 736 1050 737 1610 738 1520 739 1479 740 1596 741 1186 742 1462 743 1274 744 1400 745 1491 746 1194 747 1495 748 1728 749 1499 750 1260 751 1202 752 1505 753 1647 754 1428 755 1511 756 1210 757 1300 758 1540 759 1658 760 1521 761 1176 762 1470 763 1554 764 1310 765 1531 766 1316 767 1512 768 1537 769 1570 770 1641 771 1106 772 1545 773 1464 774 1549 775 1596 776 1242 777 1592 778 1264 779 1680 780 1561 781 1330 782 1540 783 1567 784 1540 785 1346 786 1300 787 1575 788 1554 789 1579 790 1612 791 1232 792 1512 793 1564 794 1660 795 1496 796 1274 797 1595 798 1597 799 1370 800 1601 801 1282 802 1605 803 1754 804 1568 805 1736 806 1118 807 1615 808 1617 809 1619 810 1586 811 1260 812 1520 813 1394 814 1778 815 1631 816 1306 817 1708 818 1764 819 1668 820 1372 821 1314 822 1645 823 1647 824 1688 825 1802 826 1322 827 1418 828 1690 829 1560 830 1572 831 1428 832 1665 833 1694 834 1430 835 1671 836 1554 837 1650 838 1677 839 1679 840 1756 841 1156 842 1685 843 1630 844 1820 845 1666 846 1280 847 1807 848 1454 849 1596 850 1701 851 1364 852 1660 853 1707 854 1709 855 1505 856 1370 857 1848 858 1874 859 1719 860 1746 861 1449 862 1478 863 1664 864 1729 865 1731 866 1386 867 1760 868 1644 869 1620 870 1876 871 1408 872 1745 873 1747 874 1690 875 1751 876 1204 877 1755 878 1694 879 1759 880 1792 881 1410 882 1765 883 1624 884 1769 885 1742 886 1596 887 1715 888 1777 889 1779 890 1512 891 1552 892 1785 893 1740 894 1789 895 1791 896 1540 897 1456 898 1797 899 1799 900 1801 901 1442 902 1995 903 1807 904 1591 905 1750 906 1380 907 1750 908 1817 909 2072 910 1821 911 1302 912 1860 913 1994 914 1720 915 1806 916 1456 917 1862 918 1584 919 1839 920 1841 921 1474 922 2013 923 1900 924 2018 925 1512 926 1482 927 1855 928 1857 929 1859 930 1836 931 1408 932 1656 933 1820 934 1820 935 2212 936 1470 937 1850 938 1850 939 1610 940 1881 941 1506 942 1885 943 1887 944 1788 945 1891 946 1440 947 1895 948 1904 949 1899 950 1901 951 1522 952 1905 953 1677 954 1909 955 1996 956 1530 957 2090 958 1917 959 1919 960 1672 961 1764 962 1925 963 1824 964 1898 965 1792 966 1546 967 1620 968 2114 969 1898 970 1941 971 1554 972 1945 973 1984 974 1792 975 1900 976 1540 977 1955 978 2044 979 2138 980 1961 981 1348 982 1776 983 1967 984 1969 985 1936 986 1659 987 2128 988 1694 989 1979 990 2162 991 1586 992 1985 993 1960 994 1918 995 1706 996 1594 997 2052 998 1930 999 1911 1000 2156