1 1 2 2 3 3 4 5 5 4 6 9 7 25 8 8 9 21 10 55 11 16 12 7 13 11 14 6 15 35 16 121 17 12 18 49 19 143 20 10 21 63 22 13 23 20 24 27 25 91 26 22 27 15 28 119 29 26 30 33 31 17 32 14 33 39 34 85 35 28 36 57 37 65 38 32 39 19 40 45 41 34 42 133 43 69 44 40 45 77 46 23 47 18 48 175 49 253 50 24 51 95 52 161 53 36 54 125 55 203 56 38 57 75 58 29 59 44 60 51 61 145 62 46 63 81 64 155 65 52 66 87 67 31 68 50 69 99 70 217 71 58 72 111 73 245 74 62 75 37 76 105 77 64 78 407 79 93 80 56 81 185 82 117 83 68 84 115 85 123 86 74 87 215 88 41 89 42 90 43 91 205 92 48 93 301 94 235 95 54 96 259 97 47 98 30 99 287 100 517 101 60 102 343 103 187 104 72 105 329 106 209 107 78 108 371 109 275 110 76 111 53 112 135 113 82 114 583 115 129 116 70 117 319 118 141 119 80 120 341 121 147 122 86 123 403 124 153 125 88 126 169 127 159 128 92 129 221 130 165 131 94 132 247 133 177 134 98 135 299 136 59 137 66 138 325 139 413 140 96 141 265 142 427 143 102 144 295 145 61 146 84 147 335 148 671 149 104 150 67 151 183 152 100 153 469 154 171 155 106 156 385 157 201 158 116 159 305 160 189 161 118 162 355 163 207 164 112 165 71 166 195 167 122 168 497 169 219 170 110 171 553 172 73 173 90 174 79 175 511 176 108 177 395 178 539 179 114 180 365 181 451 182 124 183 225 184 473 185 128 186 213 187 559 188 134 189 231 190 377 191 136 192 237 193 455 194 142 195 243 196 415 197 146 198 261 199 83 200 130 201 267 202 581 203 148 204 89 205 249 206 140 207 979 208 279 209 152 210 445 211 273 212 158 213 425 214 291 215 154 216 289 217 97 218 120 219 323 220 679 221 132 222 361 223 485 224 126 225 437 226 505 227 144 228 391 229 101 230 150 231 493 232 707 233 138 234 527 235 623 236 156 237 589 238 595 239 162 240 551 241 515 242 164 243 399 244 103 245 160 246 297 247 721 248 166 249 255 250 637 251 172 252 285 253 481 254 176 255 303 256 533 257 170 258 309 259 611 260 178 261 315 262 689 263 184 264 321 265 715 266 188 267 107 268 345 269 182 270 1177 271 327 272 190 273 649 274 109 275 168 276 605 277 1417 278 174 279 475 280 763 281 186 282 535 283 791 284 192 285 545 286 113 287 194 288 375 289 1243 290 196 291 333 292 565 293 202 294 351 295 575 296 206 297 339 298 529 299 200 300 357 301 667 302 208 303 363 304 713 305 212 306 369 307 775 308 214 309 381 310 625 311 218 312 127 313 405 314 224 315 1397 316 387 317 226 318 635 319 393 320 232 321 665 322 131 323 198 324 685 325 917 326 204 327 137 328 655 329 216 330 959 331 695 332 222 333 749 334 139 335 180 336 833 337 1529 338 228 339 629 340 737 341 210 342 697 343 781 344 230 345 459 346 803 347 236 348 411 349 847 350 244 351 417 352 805 353 242 354 423 355 725 356 238 357 429 358 745 359 248 360 441 361 149 362 220 363 453 364 1043 365 250 366 151 367 447 368 254 369 755 370 471 371 256 372 815 373 157 374 234 375 163 376 785 377 246 378 1141 379 835 380 258 381 889 382 167 383 240 384 931 385 1837 386 260 387 483 388 869 389 262 390 435 391 913 392 266 393 465 394 1067 395 268 396 477 397 935 398 274 399 489 400 731 401 278 402 495 403 799 404 284 405 501 406 893 407 272 408 507 409 703 410 280 411 519 412 779 413 286 414 173 415 513 416 290 417 1211 418 531 419 292 420 865 421 537 422 296 423 845 424 179 425 252 426 767 427 895 428 264 429 793 430 875 431 276 432 871 433 905 434 282 435 923 436 181 437 270 438 949 439 1267 440 288 441 1027 442 973 443 298 444 585 445 1057 446 304 447 543 448 1001 449 302 450 549 451 1015 452 314 453 561 454 841 455 310 456 567 457 1073 458 316 459 525 460 851 461 326 462 573 463 925 464 308 465 191 466 555 467 322 468 2101 469 579 470 320 471 1111 472 193 473 294 474 1045 475 2509 476 306 477 817 478 965 479 312 480 989 481 955 482 318 483 943 484 985 485 324 486 1081 487 197 488 300 489 1127 490 2167 491 328 492 609 493 1133 494 332 495 591 496 1199 497 334 498 597 499 1265 500 338 501 199 502 615 503 344 504 1393 505 603 506 340 507 1099 508 621 509 346 510 1085 511 627 512 356 513 899 514 633 515 350 516 961 517 211 518 330 519 1147 520 1477 521 342 522 1271 523 1055 524 336 525 1189 526 995 527 352 528 783 529 1025 530 358 531 639 532 1075 533 362 534 651 535 1105 536 368 537 657 538 901 539 364 540 645 541 1003 542 376 543 669 544 1037 545 370 546 223 547 663 548 380 549 1561 550 681 551 374 552 1115 553 227 554 348 555 1145 556 1589 557 354 558 229 559 1135 560 366 561 1603 562 1165 563 372 564 1169 565 233 566 360 567 1183 568 2563 569 382 570 735 571 1331 572 386 573 675 574 1309 575 388 576 687 577 1139 578 392 579 699 580 1207 581 394 582 693 583 1241 584 398 585 705 586 1343 587 404 588 717 589 1411 590 400 591 239 592 747 593 406 594 1195 595 711 596 412 597 1175 598 723 599 416 600 1225 601 241 602 384 603 1235 604 1687 605 396 606 1007 607 1205 608 378 609 1121 610 1255 611 402 612 1159 613 251 614 390 615 1273 616 1757 617 408 618 1349 619 1253 620 410 621 741 622 1337 623 422 624 729 625 1295 626 418 627 753 628 1285 629 424 630 759 631 257 632 428 633 765 634 1799 635 436 636 789 637 1351 638 430 639 263 640 777 641 440 642 3419 643 771 644 434 645 1079 646 795 647 446 648 1157 649 807 650 448 651 1261 652 269 653 414 654 1313 655 1345 656 426 657 1339 658 1315 659 432 660 1391 661 1325 662 438 663 1469 664 1219 665 420 666 1573 667 1357 668 444 669 1375 670 1403 671 442 672 825 673 1541 674 452 675 801 676 1495 677 454 678 813 679 1385 680 458 681 271 682 277 683 450 684 1897 685 3047 686 456 687 1355 688 1441 689 464 690 855 691 1507 692 466 693 819 694 1595 695 472 696 831 697 1247 698 460 699 837 700 1363 701 476 702 843 703 1457 704 478 705 281 706 987 707 482 708 1405 709 849 710 484 711 1435 712 283 713 468 714 1379 715 1415 716 474 717 1421 718 1445 719 486 720 1463 721 1465 722 488 723 861 724 293 725 470 726 867 727 2051 728 494 729 873 730 1505 731 496 732 879 733 1475 734 502 735 891 736 1525 737 508 738 897 739 1535 740 512 741 903 742 307 743 500 744 909 745 2149 746 506 747 885 748 1519 749 514 750 915 751 1333 752 518 753 921 754 1643 755 490 756 927 757 1537 758 520 759 933 760 1711 761 524 762 311 763 957 764 526 765 1555 766 939 767 532 768 1585 769 313 770 462 771 317 772 1565 773 492 774 2219 775 1615 776 498 777 1631 778 1387 779 480 780 1547 781 1501 782 516 783 1513 784 1577 785 504 786 1649 787 1691 788 522 789 1717 790 1729 791 528 792 1751 793 1625 794 534 795 1819 796 1645 797 536 798 963 799 1655 800 538 801 951 802 331 803 530 804 969 805 2317 806 542 807 975 808 1673 809 544 810 981 811 1715 812 548 813 993 814 1675 815 554 816 999 817 1685 818 556 819 1017 820 337 821 550 822 1029 823 4381 824 562 825 945 826 1651 827 566 828 1005 829 1703 830 568 831 1011 832 1781 833 560 834 1023 835 1807 836 574 837 1035 838 1859 839 578 840 1041 841 1639 842 580 843 347 844 1089 845 584 846 1735 847 1047 848 572 849 1765 850 349 851 546 852 353 853 1745 854 552 855 2471 856 1705 857 564 858 1813 859 1661 860 510 861 1369 862 1727 863 540 864 1517 865 1771 866 558 867 1591 868 1633 869 570 870 1739 871 1679 872 576 873 1927 874 1817 875 582 876 1681 877 1909 878 586 879 1107 880 1955 881 592 882 1053 883 1775 884 596 885 1059 886 1795 887 598 888 1071 889 359 890 590 891 1083 892 2513 893 604 894 1065 895 1841 896 608 897 1077 898 1855 899 614 900 1101 901 1805 902 602 903 367 904 1095 905 616 906 4771 907 1119 908 610 909 1937 910 373 911 588 912 1885 913 4103 914 606 915 1769 916 1793 917 600 918 1891 919 1903 920 612 921 1829 922 1925 923 618 924 2077 925 1825 926 594 927 1943 928 1835 929 622 930 1131 931 1865 932 626 933 1113 934 1895 935 628 936 1143 937 379 938 620 939 1149 940 2653 941 632 942 383 943 1137 944 634 945 1915 946 1161 947 638 948 1945 949 1173 950 652 951 389 952 1125 953 644 954 4279 955 1179 956 640 957 1969 958 1167 959 646 960 1991 961 1185 962 656 963 2057 964 1191 965 650 966 1853 967 397 968 624 969 1921 970 1985 971 636 972 2023 973 1975 974 642 975 1883 976 2005 977 648 978 1939 979 401 980 654 981 1967 982 4411 983 662 984 1197 985 2035 986 664 987 1203 988 1961 989 658 990 1209 991 2173 992 668 993 1155 994 1763 995 674 996 1215 997 1849 998 676 999 1221 1000 2021 1001 670 1002 1227 1003 2107 1004 680 1005 409 1006 1239 1007 682 1008 2045 1009 1233 1010 686 1011 2015 1012 1251 1013 688 1014 1963 1015 1245 1016 692 1017 2041 1018 1257 1019 694 1020 2093 1021 419 1022 660 1023 1981 1024 5447 1025 666 1026 2009 1027 2095 1028 678 1029 2177 1030 2075 1031 684 1032 2191 1033 2105 1034 696 1035 2261 1036 421 1037 690 1038 1843 1039 2947 1040 698 1041 1311 1042 2065 1043 704 1044 1263 1045 2125 1046 706 1047 1269 1048 2135 1049 712 1050 1287 1051 2155 1052 716 1053 1281 1054 431 1055 710 1056 1299 1057 3017 1058 718 1059 433 1060 1293 1061 700 1062 4763 1063 1317 1064 722 1065 2123 1066 439 1067 630 1068 2189 1069 5707 1070 672 1071 2255 1072 2119 1073 708 1074 2165 1075 2171 1076 714 1077 2185 1078 2197 1079 724 1080 1275 1081 2249 1082 734 1083 1305 1084 2327 1085 736 1086 1323 1087 2353 1088 730 1089 1329 1090 2431 1091 740 1092 443 1093 1353 1094 728 1095 2215 1096 1341 1097 742 1098 2195 1099 1347 1100 746 1101 2225 1102 449 1103 702 1104 2047 1105 2245 1106 726 1107 2231 1108 2275 1109 732 1110 2323 1111 2233 1112 720 1113 1919 1114 2059 1115 738 1116 1957 1117 2117 1118 744 1119 2033 1120 2291 1121 748 1122 1425 1123 2407 1124 752 1125 1335 1126 2573 1127 754 1128 1359 1129 2201 1130 758 1131 1365 1132 2263 1133 764 1134 1371 1135 2387 1136 760 1137 457 1138 1407 1139 766 1140 2285 1141 1377 1142 772 1143 2305 1144 1389 1145 776 1146 461 1147 463 1148 750 1149 3227 1150 5093 1151 762 1152 2303 1153 2299 1154 768 1155 2209 1156 2071 1157 756 1158 2491 1159 2147 1160 770 1161 1431 1162 2413 1163 778 1164 1383 1165 2159 1166 784 1167 1395 1168 2227 1169 788 1170 1401 1171 2329 1172 790 1173 467 1174 1479 1175 794 1176 2335 1177 1413 1178 782 1179 2315 1180 1419 1181 796 1182 2345 1183 1437 1184 802 1185 2359 1186 479 1187 774 1188 2401 1189 2395 1190 786 1191 2429 1192 2365 1193 804 1194 2443 1195 2279 1196 780 1197 2527 1198 2537 1199 792 1200 2375 1201 2183 1202 806 1203 1455 1204 2257 1205 808 1206 1449 1207 2405 1208 818 1209 1461 1210 2425 1211 812 1212 487 1213 1485 1214 824 1215 3409 1216 1443 1217 800 1218 2569 1219 1467 1220 814 1221 2485 1222 1473 1223 832 1224 2435 1225 491 1226 798 1227 2465 1228 5401 1229 822 1230 2363 1231 2321 1232 810 1233 2533 1234 2453 1235 820 1236 1581 1237 2497 1238 826 1239 1497 1240 2519 1241 830 1242 499 1243 1551 1244 838 1245 2495 1246 1491 1247 836 1248 2455 1249 1503 1250 842 1251 2515 1252 1521 1253 844 1254 503 1255 1515 1256 848 1257 3521 1258 1527 1259 850 1260 2597 1261 509 1262 816 1263 2555 1264 5599 1265 828 1266 2525 1267 2629 1268 834 1269 2545 1270 2651 1271 846 1272 2575 1273 2717 1274 852 1275 2369 1276 2483 1277 840 1278 2461 1279 2561 1280 854 1281 1587 1282 2587 1283 856 1284 1509 1285 2639 1286 860 1287 1539 1288 2581 1289 862 1290 1533 1291 2755 1292 866 1293 1557 1294 2489 1295 868 1296 1545 1297 2603 1298 872 1299 1563 1300 2641 1301 878 1302 521 1303 1653 1304 880 1305 3647 1306 1569 1307 874 1308 2605 1309 523 1310 858 1311 2635 1312 3661 1313 864 1314 2449 1315 2611 1316 870 1317 2759 1318 2681 1319 876 1320 2945 1321 2723 1322 884 1323 1605 1324 2779 1325 886 1326 1593 1327 2695 1328 892 1329 1599 1330 2585 1331 896 1332 1611 1333 2615 1334 898 1335 1617 1336 2645 1337 904 1338 1623 1339 2507 1340 890 1341 541 1342 1863 1343 902 1344 2705 1345 1629 1346 908 1347 2665 1348 1641 1349 914 1350 2419 1351 547 1352 882 1353 2501 1354 2735 1355 888 1356 2623 1357 2675 1358 894 1359 2867 1360 2725 1361 906 1362 2773 1363 2765 1364 912 1365 3127 1366 2737 1367 900 1368 2809 1369 2567 1370 910 1371 1749 1372 2669 1373 916 1374 1575 1375 2771 1376 922 1377 1635 1378 2839 1379 926 1380 1647 1381 2873 1382 920 1383 1659 1384 2743 1385 928 1386 1665 1387 2821 1388 932 1389 1671 1390 2795 1391 934 1392 557 1393 1677 1394 938 1395 2785 1396 1683 1397 944 1398 2815 1399 1701 1400 946 1401 563 1402 1695 1403 952 1404 6193 1405 1707 1406 940 1407 2761 1408 569 1409 918 1410 2783 1411 2845 1412 936 1413 2599 1414 2855 1415 924 1416 2921 1417 571 1418 930 1419 3013 1420 3997 1421 942 1422 2875 1423 2807 1424 948 1425 2825 1426 2849 1427 954 1428 2885 1429 2479 1430 956 1431 577 1432 1809 1433 950 1434 4039 1435 1689 1436 958 1437 2863 1438 1713 1439 962 1440 2891 1441 1719 1442 964 1443 2905 1444 1731 1445 968 1446 2933 1447 1725 1448 974 1449 2989 1450 1737 1451 970 1452 3031 1453 1761 1454 976 1455 2975 1456 587 1457 972 1458 2915 1459 4109 1460 978 1461 2827 1462 2935 1463 966 1464 2893 1465 2965 1466 982 1467 1881 1468 593 1469 980 1470 1767 1471 6523 1472 986 1473 1743 1474 2959 1475 988 1476 1773 1477 2981 1478 992 1479 1755 1480 3091 1481 994 1482 1779 1483 3025 1484 998 1485 1791 1486 2995 1487 1004 1488 1803 1489 599 1490 1000 1491 601 1492 1797 1493 1006 1494 3005 1495 1821 1496 1012 1497 3055 1498 607 1499 984 1500 2899 1501 3035 1502 996 1503 2951 1504 3065 1505 1002 1506 2977 1507 613 1508 960 1509 3029 1510 4291 1511 990 1512 3107 1513 3059 1514 1010 1515 1833 1516 2831 1517 1016 1518 1785 1519 2869 1520 1018 1521 1815 1522 2983 1523 1022 1524 1839 1525 3097 1526 1024 1527 1827 1528 3173 1529 1028 1530 1845 1531 3211 1532 1034 1533 1851 1534 3133 1535 1030 1536 617 1537 1911 1538 1042 1539 3085 1540 1857 1541 1036 1542 3125 1543 619 1544 1008 1545 3145 1546 6809 1547 1014 1548 2627 1549 3095 1550 1026 1551 2701 1552 3115 1553 1032 1554 2923 1555 3073 1556 1020 1557 3071 1558 3101 1559 1038 1560 3293 1561 3143 1562 1040 1563 1887 1564 3157 1565 1046 1566 1875 1567 2747 1568 1048 1569 1869 1570 2881 1571 1052 1572 1893 1573 3053 1574 1054 1575 631 1576 1917 1577 1058 1578 3155 1579 1899 1580 1064 1581 3175 1582 1923 1583 1066 1584 3215 1585 641 1586 1044 1587 643 1588 3205 1589 1056 1590 4501 1591 3235 1592 1062 1593 3199 1594 647 1595 1060 1596 1953 1597 7117 1598 1070 1599 1929 1600 3113 1601 1072 1602 1905 1603 3179 1604 1076 1605 1935 1606 2941 1607 1078 1608 1941 1609 3043 1610 1082 1611 1947 1612 3077 1613 1084 1614 1959 1615 3247 1616 1090 1617 653 1618 1989 1619 1094 1620 3265 1621 1971 1622 1088 1623 3185 1624 1977 1625 1096 1626 3241 1627 659 1628 1068 1629 3269 1630 3295 1631 1074 1632 3283 1633 3245 1634 1086 1635 3149 1636 3223 1637 1050 1638 3337 1639 3289 1640 1080 1641 2911 1642 3151 1643 1092 1644 2993 1645 3197 1646 1098 1647 3139 1648 3335 1649 1106 1650 2193 1651 2813 1652 1100 1653 1983 1654 2929 1655 1108 1656 661 1657 2001 1658 1112 1659 3305 1660 2007 1661 1102 1662 3275 1663 2013 1664 1114 1665 3325 1666 2019 1667 1118 1668 3287 1669 673 1670 1104 1671 3401 1672 3365 1673 1116 1674 3439 1675 3355 1676 1124 1677 2109 1678 3233 1679 1120 1680 2031 1681 3551 1682 1126 1683 677 1684 2067 1685 1130 1686 4739 1687 2043 1688 1132 1689 3311 1690 1965 1691 1136 1692 3353 1693 2025 1694 1138 1695 3367 1696 2049 1697 1142 1698 3263 1699 683 1700 1110 1701 3341 1702 4781 1703 1122 1704 3445 1705 3437 1706 1128 1707 3385 1708 3451 1709 1144 1710 2055 1711 2987 1712 1148 1713 2061 1714 3103 1715 1150 1716 2037 1717 3161 1718 1154 1719 1995 1720 3277 1721 1156 1722 2073 1723 3503 1724 1160 1725 691 1726 2139 1727 1162 1728 3455 1729 2091 1730 1166 1731 3395 1732 2097 1733 1168 1734 3007 1735 2079 1736 1172 1737 3131 1738 2085 1739 1174 1740 3193 1741 2103 1742 1180 1743 3317 1744 701 1745 1134 1746 3379 1747 3505 1748 1146 1749 3689 1750 3415 1751 1152 1752 3281 1753 3425 1754 1164 1755 3349 1756 3475 1757 1158 1758 3383 1759 3515 1760 1176 1761 3587 1762 3545 1763 1178 1764 2397 1765 709 1766 1184 1767 2115 1768 4963 1769 1186 1770 2133 1771 3479 1772 1192 1773 2127 1774 3493 1775 1196 1776 2151 1777 3535 1778 1198 1779 2157 1780 3485 1781 1202 1782 719 1783 2145 1784 1204 1785 12223 1786 2169 1787 1208 1788 3553 1789 2121 1790 1214 1791 3377 1792 2163 1793 1216 1794 3421 1795 2175 1796 1222 1797 3443 1798 2181 1799 1190 1800 3487 1801 727 1802 1140 1803 3509 1804 5089 1805 1170 1806 3641 1807 3563 1808 1182 1809 3575 1810 3577 1811 1194 1812 3497 1813 3431 1814 1188 1815 3523 1816 3713 1817 1200 1818 3601 1819 3239 1820 1206 1821 3653 1822 3397 1823 1210 1824 2223 1825 3569 1826 1220 1827 2187 1828 3403 1829 1226 1830 2199 1831 3649 1832 1228 1833 733 1834 2337 1835 1232 1836 3665 1837 2217 1838 1234 1839 3565 1840 739 1841 1212 1842 3427 1843 3695 1844 1218 1845 3473 1846 3595 1847 1224 1848 3611 1849 3605 1850 1238 1851 2277 1852 3625 1853 1244 1854 2211 1855 3635 1856 1246 1857 2229 1858 3655 1859 1252 1860 743 1861 2205 1862 1256 1863 8173 1864 2235 1865 1258 1866 3619 1867 2241 1868 1240 1869 3703 1870 2253 1871 1250 1872 3731 1873 751 1874 1236 1875 3679 1876 3755 1877 1242 1878 3757 1879 3685 1880 1262 1881 2301 1882 3707 1883 1264 1884 2247 1885 3751 1886 1268 1887 2259 1888 3773 1889 1270 1890 2271 1891 3787 1892 1276 1893 757 1894 2289 1895 1280 1896 8327 1897 2283 1898 1274 1899 3785 1900 761 1901 1248 1902 3715 1903 5327 1904 1254 1905 3725 1906 3829 1907 1266 1908 3775 1909 3857 1910 1272 1911 3805 1912 3629 1913 1278 1914 3745 1915 3667 1916 1282 1917 2265 1918 3743 1919 1286 1920 2295 1921 3781 1922 1288 1923 2307 1924 3895 1925 1294 1926 769 1927 2325 1928 1292 1929 5383 1930 2313 1931 1298 1932 3815 1933 2319 1934 1304 1935 3835 1936 773 1937 1284 1938 3481 1939 3865 1940 1296 1941 3599 1942 3845 1943 1302 1944 3721 1945 3905 1946 1306 1947 2379 1948 3763 1949 1310 1950 2331 1951 3869 1952 1300 1953 2343 1954 4187 1955 1312 1956 2349 1957 3871 1958 1318 1959 2355 1960 3899 1961 1322 1962 2361 1963 3913 1964 1324 1965 787 1966 2373 1967 1328 1968 3935 1969 2367 1970 1316 1971 3875 1972 2391 1973 1334 1974 3925 1975 797 1976 1308 1977 3955 1978 8767 1979 1314 1980 3941 1981 3817 1982 1230 1983 3983 1984 3839 1985 1290 1986 4067 1987 3883 1988 1326 1989 3901 1990 3949 1991 1260 1992 4183 1993 3971 1994 1332 1995 3827 1996 4009 1997 1320 1998 4171 1999 4123 2000 1336