0 1 1 5 2 2 3 9 4 13 5 8 6 7 7 11 8 10 9 17 10 19 11 30 12 23 13 31 14 16 15 45 16 34 17 38 18 39 19 37 20 43 21 35 22 56 23 57 24 51 25 53 26 64 27 58 28 40 29 68 30 63 31 65 32 73 33 87 34 48 35 85 36 92 37 75 38 100 39 76 40 52 41 106 42 107 43 66 44 110 45 88 46 117 47 61 48 108 49 123 50 125 51 102 52 128 53 89 54 104 55 129 56 134 57 96 58 132 59 143 60 116 61 147 62 133 63 95 64 154 65 152 66 158 67 115 68 135 69 105 70 173 71 172 72 103 73 180 74 121 75 185 76 161 77 162 78 165 79 145 80 176 81 137 82 144 83 198 84 196 85 189 86 186 87 203 88 181 89 112 90 220 91 151 92 149 93 146 94 217 95 210 96 216 97 223 98 127 99 212 100 159 101 209 102 219 103 138 104 242 105 190 106 249 107 238 108 192 109 247 110 226 111 204 112 229 113 252 114 259 115 271 116 182 117 208 118 261 119 277 120 282 121 178 122 230 123 200 124 253 125 206 126 287 127 211 128 263 129 231 130 300 131 290 132 292 133 257 134 299 135 245 136 243 137 308 138 320 139 296 140 314 141 303 142 327 143 316 144 224 145 324 146 346 147 302 148 325 149 349 150 341 151 353 152 352 153 348 154 218 155 362 156 356 157 357 158 365 159 360 160 202 161 267 162 377 163 330 164 374 165 201 166 378 167 270 168 376 169 379 170 275 171 398 172 266 173 371 174 373 175 396 176 237 177 338 178 404 179 382 180 291 181 328 182 422 183 414 184 333 185 416 186 408 187 289 188 412 189 434 190 427 191 417 192 418 193 399 194 448 195 428 196 455 197 355 198 449 199 450 200 430 201 322 202 454 203 444 204 463 205 424 206 363 207 375 208 443 209 451 210 465 211 452 212 471 213 485 214 493 215 481 216 297 217 470 218 459 219 366 220 331 221 482 222 489 223 397 224 501 225 505 226 506 227 400 228 515 229 512 230 519 231 527 232 336 233 359 234 486 235 317 236 529 237 524 238 537 239 490 240 520 241 298 242 508 243 525 244 544 245 536 246 548 247 518 248 538 249 557 250 558 251 561 252 423 253 389 254 563 255 413 256 559 257 564 258 554 259 545 260 401 261 584 262 587 263 593 264 565 265 438 266 432 267 573 268 601 269 577 270 604 271 602 272 453 273 596 274 409 275 625 276 612 277 581 278 574 279 435 280 522 281 634 282 621 283 609 284 638 285 646 286 622 287 630 288 641 289 647 290 637 291 658 292 624 293 662 294 437 295 447 296 462 297 656 298 655 299 461 300 643 301 667 302 534 303 649 304 567 305 698 306 478 307 484 308 692 309 693 310 672 311 700 312 556 313 686 314 676 315 695 316 705 317 691 318 707 319 717 320 665 321 528 322 715 323 531 324 440 325 723 326 731 327 719 328 516 329 725 330 722 331 517 332 499 333 569 334 746 335 743 336 732 337 749 338 747 339 750 340 740 341 762 342 571 343 711 344 539 345 580 346 773 347 775 348 582 349 774 350 720 351 585 352 792 353 549 354 787 355 583 356 791 357 600 358 777 359 801 360 781 361 806 362 783 363 782 364 613 365 819 366 817 367 550 368 822 369 562 370 793 371 590 372 818 373 794 374 837 375 644 376 617 377 834 378 850 379 797 380 840 381 645 382 843 383 863 384 853 385 861 386 858 387 594 388 836 389 866 390 876 391 623 392 683 393 620 394 878 395 514 396 870 397 872 398 887 399 633 400 884 401 895 402 892 403 906 404 903 405 898 406 764 407 713 408 632 409 910 410 651 411 927 412 912 413 914 414 934 415 932 416 936 417 882 418 727 419 942 420 920 421 948 422 946 423 943 424 937 425 938 426 957 427 953 428 963 429 654 430 959 431 944 432 965 433 690 434 669 435 706 436 974 437 970 438 967 439 983 440 986 441 978 442 689 443 694 444 996 445 992 446 674 447 980 448 977 449 997 450 1000 451 1007 452 1014 453 1002 454 1003 455 1021 456 1004 457 924 458 1024 459 987 460 973 461 767 462 1026 463 975 464 991 465 1027 466 1040 467 1042 468 1005 469 1022 470 1009 471 1047 472 712 473 1050 474 748 475 741 476 1017 477 1054 478 1030 479 1029 480 1065 481 1079 482 1053 483 734 484 1072 485 821 486 755 487 828 488 807 489 1067 490 1059 491 1037 492 779 493 1055 494 1096 495 778 496 835 497 1089 498 1113 499 1063 500 684 501 1073 502 1126 503 862 504 799 505 1128 506 1136 507 1133 508 780 509 1093 510 1122 511 789 512 1123 513 795 514 1120 515 1141 516 809 517 1116 518 1156 519 1150 520 1155 521 1159 522 868 523 1153 524 1118 525 1152 526 798 527 1176 528 888 529 886 530 1173 531 802 532 829 533 890 534 826 535 1180 536 1189 537 1166 538 1188 539 1131 540 1215 541 1208 542 1139 543 1149 544 1212 545 1217 546 1219 547 1220 548 1158 549 1210 550 1202 551 1225 552 1174 553 1234 554 1165 555 1235 556 1240 557 1222 558 1142 559 1183 560 1200 561 1242 562 1044 563 889 564 995 565 1243 566 1246 567 1192 568 1255 569 958 570 1256 571 1257 572 1206 573 902 574 1273 575 921 576 933 577 1274 578 961 579 1282 580 941 581 1287 582 1275 583 1283 584 900 585 1297 586 1293 587 1236 588 1309 589 1299 590 931 591 1312 592 1302 593 1310 594 1314 595 994 596 926 597 1325 598 1226 599 1303 600 1329 601 998 602 1344 603 954 604 1025 605 1006 606 949 607 1018 608 1354 609 939 610 1331 611 1361 612 1336 613 1368 614 1364 615 1010 616 1244 617 1337 618 1335 619 1373 620 1358 621 1348 622 1383 623 1350 624 972 625 969 626 1356 627 1390 628 971 629 1272 630 1367 631 1385 632 1033 633 1380 634 964 635 1371 636 1269 637 1392 638 1400 639 1382 640 1077 641 1412 642 1423 643 1411 644 1418 645 1430 646 1091 647 1437 648 1425 649 999 650 1424 651 1441 652 1434 653 1447 654 1470 655 1410 656 1092 657 1444 658 1106 659 1098 660 1469 661 1467 662 1486 663 1036 664 1484 665 1427 666 1457 667 1439 668 1112 669 1436 670 1455 671 1048 672 1475 673 1502 674 1500 675 1515 676 1452 677 1504 678 1456 679 1514 680 1481 681 1028 682 1066 683 1146 684 1506 685 1538 686 1462 687 1466 688 1148 689 1547 690 1553 691 1157 692 1151 693 1070 694 1498 695 1291 696 1530 697 1121 698 1495 699 1489 700 1572 701 1094 702 1503 703 1476 704 1507 705 1559 706 1107 707 1589 708 1105 709 1501 710 1579 711 1539 712 1526 713 1534 714 1540 715 1097 716 1542 717 1108 718 1576 719 1324 720 1203 721 1545 722 1204 723 1554 724 1550 725 1127 726 1130 727 1555 728 1211 729 1619 730 1558 731 1561 732 1564 733 1229 734 1636 735 1562 736 1573 737 1376 738 1566 739 1645 740 1568 741 1597 742 1387 743 1184 744 1186 745 1591 746 1571 747 1662 748 1596 749 1593 750 1237 751 1233 752 1603 753 1601 754 1608 755 1616 756 1605 757 1607 758 1684 759 1162 760 1261 761 1580 762 1617 763 1612 764 1618 765 1279 766 1689 767 1699 768 1710 769 1248 770 1214 771 1632 772 1634 773 1656 774 1638 775 1643 776 1641 777 1660 778 1653 779 1668 780 1296 781 1735 782 1740 783 1664 784 1661 785 1670 786 1209 787 1748 788 1749 789 1730 790 1759 791 1320 792 1750 793 1692 794 1479 795 1761 796 1230 797 1330 798 1677 799 1773 800 1777 801 1228 802 1695 803 1702 804 1785 805 1772 806 1278 807 1788 808 1720 809 1258 810 1802 811 1792 812 1789 813 1707 814 1794 815 1714 816 1706 817 1799 818 1404 819 1808 820 1681 821 1726 822 1815 823 1736 824 1693 825 1733 826 1742 827 1836 828 1850 829 1322 830 1804 831 1752 832 1284 833 1837 834 1334 835 1832 836 1853 837 1835 838 1857 839 1751 840 1355 841 1861 842 1784 843 1775 844 1840 845 1351 846 1886 847 1841 848 1855 849 1897 850 1349 851 1838 852 1894 853 1866 854 1849 855 1883 856 1747 857 1451 858 1881 859 1876 860 1867 861 1438 862 1869 863 1863 864 1468 865 1907 866 1887 867 1879 868 1912 869 1915 870 1442 871 1916 872 1935 873 1892 874 1919 875 1473 876 1906 877 1471 878 1929 879 1378 880 1908 881 1463 882 1952 883 1763 884 1880 885 1958 886 1899 887 1904 888 1477 889 1401 890 1932 891 1986 892 1967 893 1913 894 1497 895 1934 896 1984 897 1955 898 1938 899 1365 900 1995 901 1687 902 2006 903 1496 904 1527 905 1996 906 1978 907 1417 908 2017 909 2010 910 1420 911 2023 912 1691 913 1520 914 1991 915 1976 916 1413 917 2041 918 1966 919 2043 920 1426 921 2036 922 1945 923 1997 924 2021 925 2064 926 1525 927 2046 928 2068 929 2065 930 1993 931 1575 932 2084 933 2058 934 2013 935 1577 936 2059 937 2071 938 2028 939 2072 940 1594 941 2060 942 2062 943 2030 944 2067 945 2080 946 2085 947 1600 948 2035 949 1583 950 2090 951 2089 952 1485 953 2033 954 2108 955 2050 956 1609 957 1615 958 2082 959 2052 960 2099 961 2116 962 2074 963 1624 964 2139 965 2073 966 2092 967 1839 968 2138 969 2126 970 1644 971 2132 972 2124 973 1626 974 2137 975 2140 976 2145 977 2194 978 2153 979 2142 980 1529 981 2114 982 2150 983 2113 984 2091 985 2190 986 2118 987 2143 988 1651 989 2121 990 2094 991 2110 992 2203 993 2165 994 2111 995 2225 996 2127 997 2152 998 2112 999 2157 1000 2149