1 1 2 2 3 3 4 4 5 7 6 6 7 5 8 11 9 13 10 9 11 8 12 16 13 21 14 19 15 14 16 10 17 22 18 30 19 31 20 27 21 18 22 12 23 28 24 39 25 45 26 43 27 36 28 23 29 15 30 34 31 50 32 57 33 61 34 56 35 44 36 26 37 17 38 40 39 60 40 73 41 79 42 78 43 68 44 52 45 32 46 20 47 47 48 70 49 87 50 98 51 101 52 94 53 83 54 63 55 37 56 24 57 54 58 82 59 104 60 118 61 126 62 124 63 113 64 96 65 72 66 42 67 25 68 62 69 93 70 119 71 138 72 150 73 152 74 146 75 132 76 110 77 81 78 48 79 29 80 67 81 106 82 136 83 161 84 176 85 184 86 181 87 170 88 151 89 127 90 91 91 53 92 33 93 75 94 117 95 153 96 182 97 202 98 215 99 217 100 210 101 196 102 173 103 140 104 103 105 59 106 35 107 85 108 130 109 169 110 204 111 231 112 245 113 255 114 252 115 240 116 222 117 193 118 157 119 112 120 65 121 38 122 90 123 143 124 188 125 227 126 260 127 279 128 292 129 294 130 289 131 270 132 246 133 213 134 172 135 123 136 71 137 41 138 99 139 155 140 206 141 251 142 285 143 313 144 330 145 339 146 336 147 326 148 305 149 272 150 233 151 187 152 134 153 76 154 46 155 107 156 167 157 224 158 273 159 315 160 348 161 369 162 385 163 387 164 379 165 361 166 335 167 302 168 257 169 203 170 144 171 84 172 49 173 115 174 180 175 242 176 297 177 345 178 382 179 409 180 426 181 436 182 434 183 422 184 400 185 368 186 328 187 278 188 220 189 158 190 89 191 51 192 122 193 195 194 261 195 320 196 373 197 417 198 451 199 475 200 488 201 492 202 483 203 465 204 440 205 402 206 355 207 299 208 236 209 166 210 95 211 55 212 131 213 208 214 281 215 347 216 405 217 453 218 493 219 519 220 540 221 548 222 546 223 535 224 512 225 477 226 435 227 384 228 321 229 254 230 178 231 102 232 58 233 139 234 223 235 298 236 370 237 433 238 489 239 534 240 570 241 593 242 609 243 613 244 603 245 586 246 556 247 517 248 468 249 410 250 346 251 268 252 190 253 108 254 64 255 147 256 235 257 316 258 396 259 464 260 526 261 575 262 617 263 647 264 668 265 675 266 672 267 660 268 636 269 602 270 559 271 504 272 441 273 366 274 287 275 200 276 114 277 66 278 159 279 248 280 338 281 420 282 496 283 563 284 620 285 666 286 701 287 727 288 741 289 747 290 736 291 720 292 691 293 649 294 596 295 539 296 467 297 390 298 306 299 214 300 121 301 69 302 164 303 264 304 357 305 447 306 529 307 598 308 663 309 714 310 757 311 787 312 809 313 818 314 817 315 802 316 776 317 743 318 696 319 640 320 572 321 498 322 413 323 322 324 226 325 128 326 74 327 174 328 277 329 377 330 472 331 561 332 637 333 703 334 766 335 813 336 849 337 875 338 891 339 895 340 885 341 868 342 836 343 796 344 745 345 683 346 610 347 527 348 437 349 341 350 238 351 135 352 77 353 183 354 291 355 397 356 499 357 590 358 674 359 750 360 815 361 870 362 913 363 946 364 965 365 975 366 973 367 957 368 933 369 900 370 848 371 790 372 724 373 642 374 554 375 460 376 356 377 250 378 142 379 80 380 192 381 308 382 418 383 524 384 625 385 712 386 794 387 865 388 925 389 976 390 1010 391 1041 392 1057 393 1060 394 1051 395 1032 396 1001 397 956 398 905 399 841 400 767 401 682 402 587 403 484 404 375 405 263 406 148 407 86 408 199 409 319 410 438 411 551 412 655 413 753 414 840 415 918 416 984 417 1040 418 1085 419 1116 420 1137 421 1147 422 1146 423 1130 424 1105 425 1067 426 1017 427 958 428 888 429 806 430 717 431 616 432 509 433 394 434 275 435 156 436 88 437 209 438 334 439 458 440 576 441 689 442 789 443 883 444 969 445 1042 446 1103 447 1154 448 1192 449 1221 450 1236 451 1242 452 1229 453 1212 454 1181 455 1135 456 1081 457 1011 458 937 459 850 460 754 461 646 462 532 463 412 464 286 465 162 466 92 467 218 468 350 469 478 470 604 471 723 472 831 473 930 474 1019 475 1098 476 1168 477 1224 478 1270 479 1306 480 1325 481 1336 482 1333 483 1317 484 1293 485 1254 486 1204 487 1144 488 1071 489 989 490 892 491 788 492 677 493 557 494 429 495 300 496 168 497 97 498 229 499 364 500 501 501 630 502 756 503 871 504 977 505 1074 506 1161 507 1233 508 1298 509 1351 510 1386 511 1418 512 1434 513 1437 514 1427 515 1407 516 1375 517 1329 518 1272 519 1205 520 1126 521 1038 522 935 523 828 524 708 525 582 526 449 527 311 528 177 529 100 530 237 531 380 532 518 533 657 534 786 535 910 536 1021 537 1124 538 1218 539 1301 540 1370 541 1426 542 1474 543 1508 544 1531 545 1542 546 1539 547 1522 548 1494 549 1458 550 1405 551 1345 552 1269 553 1183 554 1088 555 982 556 863 557 738 558 606 559 466 560 325 561 185 562 105 563 244 564 395 565 542 566 686 567 822 568 949 569 1070 570 1179 571 1276 572 1366 573 1443 574 1507 575 1560 576 1601 577 1627 578 1643 579 1649 580 1641 581 1619 582 1584 583 1543 584 1481 585 1415 586 1332 587 1244 588 1138 589 1024 590 904 591 771 592 631 593 486 594 337 595 191 596 109 597 256 598 408 599 564 600 711 601 856 602 992 603 1115 604 1230 605 1337 606 1432 607 1513 608 1585 609 1645 610 1690 611 1729 612 1752 613 1761 614 1757 615 1741 616 1717 617 1676 618 1622 619 1561 620 1482 621 1396 622 1300 623 1188 624 1069 625 939 626 801 627 656 628 506 629 352 630 198 631 111 632 266 633 425 634 584 635 739 636 890 637 1030 638 1164 639 1284 640 1397 641 1496 642 1587 643 1670 644 1733 645 1787 646 1826 647 1856 648 1872 649 1878 650 1867 651 1848 652 1813 653 1767 654 1707 655 1637 656 1555 657 1465 658 1358 659 1243 660 1113 661 978 662 834 663 684 664 522 665 363 666 205 667 116 668 274 669 443 670 605 671 769 672 923 673 1073 674 1211 675 1339 676 1459 677 1568 678 1666 679 1747 680 1820 681 1881 682 1930 683 1964 684 1988 685 2000 686 1996 687 1980 688 1952 689 1915 690 1860 691 1795 692 1718 693 1625 694 1525 695 1416 696 1290 697 1160 698 1013 699 864 700 705 701 544 702 376 703 212 704 120 705 283 706 455 707 627 708 795 709 955 710 1112 711 1258 712 1393 713 1519 714 1635 715 1736 716 1827 717 1909 718 1975 719 2030 720 2073 721 2102 722 2119 723 2122 724 2113 725 2090 726 2056 727 2013 728 1949 729 1880 730 1797 731 1697 732 1593 733 1472 734 1344 735 1203 736 1053 737 898 738 731 739 562 740 389 741 219 742 125 743 293 744 471 745 648 746 825 747 994 748 1153 749 1307 750 1448 751 1580 752 1700 753 1812 754 1913 755 1998 756 2072 757 2134 758 2179 759 2219 760 2241 761 2251 762 2250 763 2231 764 2205 765 2166 766 2108 767 2044 768 1966 769 1874 770 1773 771 1658 772 1533 773 1395 774 1251 775 1093 776 928 777 758 778 581 779 403 780 228 781 129 782 303 783 487 784 669 785 852 786 1029 787 1193 788 1356 789 1505 790 1642 791 1772 792 1888 793 1994 794 2085 795 2169 796 2234 797 2292 798 2335 799 2366 800 2382 801 2386 802 2377 803 2353 804 2317 805 2272 806 2211 807 2139 808 2051 809 1956 810 1845 811 1723 812 1591 813 1447 814 1295 815 1133 816 959 817 782 818 599 819 416 820 234 821 133 822 312 823 503 824 693 825 879 826 1062 827 1237 828 1400 829 1557 830 1703 831 1840 832 1963 833 2077 834 2175 835 2266 836 2339 837 2401 838 2452 839 2488 840 2510 841 2525 842 2522 843 2501 844 2476 845 2434 846 2381 847 2310 848 2229 849 2142 850 2033 851 1919 852 1790 853 1652 854 1500 855 1341 856 1172 857 996 858 810 859 621 860 428 861 241 862 137 863 323 864 516 865 713 866 908 867 1097 868 1277 869 1452 870 1614 871 1766 872 1911 873 2039 874 2161 875 2269 876 2361 877 2444 878 2511 879 2569 880 2614 881 2642 882 2660 883 2663 884 2656 885 2632 886 2596 887 2552 888 2487 889 2415 890 2325 891 2225 892 2114 893 1993 894 1853 895 1709 896 1553 897 1383 898 1210 899 1026 900 835 901 639 902 445 903 249 904 141 905 331 906 533 907 734 908 936 909 1134 910 1320 911 1499 912 1673 913 1828 914 1979 915 2116 916 2245 917 2356 918 2459 919 2550 920 2624 921 2690 922 2736 923 2777 924 2799 925 2810 926 2807 927 2792 928 2763 929 2720 930 2666 931 2594 932 2515 933 2424 934 2312 935 2197 936 2066 937 1923 938 1771 939 1605 940 1433 941 1252 942 1058 943 860 944 658 945 456 946 258 947 145 948 342 949 550 950 760 951 966 952 1167 953 1363 954 1548 955 1726 956 1895 957 2047 958 2192 959 2327 960 2449 961 2558 962 2652 963 2734 964 2806 965 2865 966 2907 967 2938 968 2959 969 2962 970 2954 971 2929 972 2892 973 2845 974 2782 975 2706 976 2617 977 2520 978 2404 979 2281 980 2143 981 1991 982 1829 983 1662 984 1477 985 1287 986 1091 987 887 988 680 989 469 990 265 991 149 992 353 993 566 994 780 995 997 996 1202 997 1403 998 1597 999 1784 1000 1957 1001 2120 1002 2271 1003 2412 1004 2542 1005 2657 1006 2760 1007 2854 1008 2924 1009 2992 1010 3042 1011 3080 1012 3104 1013 3117 1014 3114 1015 3095 1016 3068 1017 3025 1018 2971 1019 2898 1020 2815 1021 2721 1022 2615 1023 2491 1024 2359 1025 2217 1026 2058 1027 1892 1028 1712 1029 1523 1030 1328 1031 1121 1032 915 1033 699 1034 481 1035 271 1036 154 1037 360 1038 580 1039 803 1040 1022 1041 1241 1042 1446 1043 1648 1044 1838 1045 2020 1046 2186 1047 2349 1048 2497 1049 2631 1050 2754 1051 2867 1052 2964 1053 3047 1054 3123 1055 3176 1056 3224 1057 3253 1058 3270 1059 3274 1060 3265 1061 3239 1062 3206 1063 3158 1064 3092 1065 3016 1066 2925 1067 2825 1068 2708 1069 2578 1070 2440 1071 2290 1072 2127 1073 1950 1074 1765 1075 1573 1076 1368 1077 1159 1078 940 1079 718 1080 497 1081 280 1082 160 1083 371 1084 595 1085 826 1086 1052 1087 1275 1088 1490 1089 1694 1090 1896 1091 2082 1092 2263 1093 2428 1094 2579 1095 2724 1096 2857 1097 2974 1098 3076 1099 3170 1100 3244 1101 3314 1102 3363 1103 3400 1104 3428 1105 3440 1106 3435 1107 3419 1108 3389 1109 3343 1110 3292 1111 3221 1112 3136 1113 3039 1114 2928 1115 2805 1116 2675 1117 2526 1118 2367 1119 2193 1120 2014 1121 1821 1122 1618 1123 1409 1124 1189 1125 967 1126 737 1127 510 1128 288 1129 163 1130 381 1131 615 1132 846 1133 1082 1134 1310 1135 1534 1136 1746 1137 1951 1138 2148 1139 2332 1140 2503 1141 2669 1142 2817 1143 2956 1144 3079 1145 3189 1146 3293 1147 3377 1148 3448 1149 3508 1150 3552 1151 3582 1152 3601 1153 3607 1154 3596 1155 3574 1156 3537 1157 3487 1158 3422 1159 3340 1160 3256 1161 3150 1162 3032 1163 2905 1164 2761 1165 2609 1166 2438 1167 2264 1168 2075 1169 1875 1170 1669 1171 1449 1172 1222 1173 995 1174 759 1175 523 1176 296 1177 165 1178 392 1179 629 1180 872 1181 1110 1182 1348 1183 1577 1184 1799 1185 2011 1186 2213 1187 2405 1188 2585 1189 2752 1190 2910 1191 3054 1192 3185 1193 3309 1194 3415 1195 3506 1196 3583 1197 3650 1198 3706 1199 3742 1200 3767 1201 3781 1202 3778 1203 3758 1204 3728 1205 3685 1206 3630 1207 3557 1208 3474 1209 3373 1210 3263 1211 3141 1212 3002 1213 2856 1214 2692 1215 2519 1216 2331 1217 2135 1218 1931 1219 1713 1220 1487 1221 1257 1222 1018 1223 778 1224 538 1225 304 1226 171 1227 401 1228 645 1229 893 1230 1142 1231 1382 1232 1617 1233 1847 1234 2069 1235 2279 1236 2475 1237 2662 1238 2841 1239 3006 1240 3156 1241 3299 1242 3421 1243 3533 1244 3639 1245 3720 1246 3796 1247 3851 1248 3903 1249 3933 1250 3951 1251 3955 1252 3944 1253 3920 1254 3887 1255 3835 1256 3770 1257 3691 1258 3598 1259 3494 1260 3376 1261 3240 1262 3098 1263 2944 1264 2775 1265 2592 1266 2400 1267 2199 1268 1983 1269 1762 1270 1530 1271 1288 1272 1045 1273 800 1274 552 1275 310 1276 175 1277 411 1278 661 1279 917 1280 1170 1281 1420 1282 1664 1283 1898 1284 2124 1285 2340 1286 2548 1287 2741 1288 2923 1289 3097 1290 3257 1291 3404 1292 3538 1293 3661 1294 3765 1295 3859 1296 3942 1297 4010 1298 4060 1299 4099 1300 4124 1301 4138 1302 4135 1303 4118 1304 4084 1305 4041 1306 3986 1307 3914 1308 3827 1309 3724 1310 3617 1311 3489 1312 3348 1313 3197 1314 3034 1315 2859 1316 2671 1317 2469 1318 2259 1319 2037 1320 1807 1321 1571 1322 1323 1323 1076 1324 820 1325 567 1326 317 1327 179 1328 421 1329 679 1330 938 1331 1198 1332 1456 1333 1704 1334 1945 1335 2180 1336 2406 1337 2620 1338 2822 1339 3012 1340 3192 1341 3360 1342 3514 1343 3654 1344 3786 1345 3899 1346 4000 1347 4086 1348 4162 1349 4220 1350 4267 1351 4301 1352 4319 1353 4326 1354 4314 1355 4289 1356 4251 1357 4200 1358 4136 1359 4052 1360 3962 1361 3853 1362 3734 1363 3603 1364 3457 1365 3300 1366 3126 1367 2942 1368 2745 1369 2539 1370 2319 1371 2094 1372 1854 1373 1610 1374 1361 1375 1099 1376 839 1377 578 1378 327 1379 186 1380 431 1381 695 1382 961 1383 1228 1384 1492 1385 1751 1386 2001 1387 2239 1388 2470 1389 2694 1390 2903 1391 3101 1392 3289 1393 3461 1394 3624 1395 3773 1396 3910 1397 4029 1398 4139 1399 4230 1400 4316 1401 4382 1402 4439 1403 4472 1404 4501 1405 4513 1406 4508 1407 4491 1408 4460 1409 4416 1410 4361 1411 4284 1412 4199 1413 4098 1414 3988 1415 3856 1416 3715 1417 3562 1418 3396 1419 3219 1420 3027 1421 2823 1422 2610 1423 2385 1424 2151 1425 1904 1426 1654 1427 1392 1428 1127 1429 858 1430 592 1431 333 1432 189 1433 444 1434 710 1435 986 1436 1259 1437 1527 1438 1793 1439 2049 1440 2299 1441 2537 1442 2767 1443 2984 1444 3186 1445 3384 1446 3564 1447 3733 1448 3891 1449 4032 1450 4164 1451 4277 1452 4381 1453 4468 1454 4548 1455 4604 1456 4653 1457 4686 1458 4702 1459 4708 1460 4698 1461 4673 1462 4634 1463 4584 1464 4520 1465 4440 1466 4342 1467 4232 1468 4115 1469 3981 1470 3833 1471 3671 1472 3498 1473 3313 1474 3110 1475 2899 1476 2683 1477 2445 1478 2204 1479 1954 1480 1691 1481 1425 1482 1155 1483 880 1484 608 1485 343 1486 194 1487 452 1488 728 1489 1007 1490 1286 1491 1567 1492 1836 1493 2101 1494 2354 1495 2601 1496 2840 1497 3061 1498 3275 1499 3479 1500 3666 1501 3843 1502 4009 1503 4160 1504 4295 1505 4418 1506 4531 1507 4621 1508 4706 1509 4776 1510 4829 1511 4868 1512 4896 1513 4908 1514 4903 1515 4887 1516 4855 1517 4806 1518 4753 1519 4677 1520 4589 1521 4486 1522 4375 1523 4242 1524 4101 1525 3945 1526 3779 1527 3595 1528 3399 1529 3195 1530 2980 1531 2747 1532 2507 1533 2262 1534 2004 1535 1734 1536 1463 1537 1182 1538 903 1539 623 1540 351 1541 197 1542 461 1543 746 1544 1031 1545 1316 1546 1604 1547 1882 1548 2153 1549 2416 1550 2670 1551 2911 1552 3145 1553 3364 1554 3573 1555 3772 1556 3954 1557 4126 1558 4282 1559 4429 1560 4558 1561 4676 1562 4781 1563 4871 1564 4947 1565 5008 1566 5056 1567 5087 1568 5109 1569 5113 1570 5104 1571 5074 1572 5038 1573 4986 1574 4918 1575 4838 1576 4744 1577 4632 1578 4510 1579 4376 1580 4224 1581 4062 1582 3888 1583 3696 1584 3495 1585 3282 1586 3056 1587 2819 1588 2573 1589 2313 1590 2048 1591 1777 1592 1493 1593 1208 1594 921 1595 634 1596 358 1597 201 1598 473 1599 763 1600 1055 1601 1352 1602 1640 1603 1926 1604 2203 1605 2472 1606 2732 1607 2987 1608 3226 1609 3452 1610 3669 1611 3871 1612 4067 1613 4243 1614 4408 1615 4564 1616 4700 1617 4827 1618 4936 1619 5032 1620 5120 1621 5185 1622 5242 1623 5281 1624 5305 1625 5318 1626 5315 1627 5298 1628 5268 1629 5221 1630 5163 1631 5086 1632 5000 1633 4898 1634 4780 1635 4649 1636 4506 1637 4348 1638 4179 1639 3997 1640 3798 1641 3587 1642 3365 1643 3135 1644 2889 1645 2637 1646 2374 1647 2098 1648 1817 1649 1529 1650 1238 1651 943 1652 650 1653 365 1654 207 1655 482 1656 775 1657 1078 1658 1378 1659 1678 1660 1969 1661 2256 1662 2534 1663 2800 1664 3059 1665 3308 1666 3542 1667 3764 1668 3978 1669 4178 1670 4363 1671 4541 1672 4696 1673 4842 1674 4977 1675 5096 1676 5194 1677 5291 1678 5368 1679 5428 1680 5475 1681 5508 1682 5532 1683 5536 1684 5525 1685 5499 1686 5457 1687 5404 1688 5341 1689 5258 1690 5161 1691 5051 1692 4929 1693 4787 1694 4636 1695 4471 1696 4292 1697 4102 1698 3900 1699 3680 1700 3453 1701 3215 1702 2963 1703 2700 1704 2429 1705 2147 1706 1858 1707 1564 1708 1265 1709 962 1710 664 1711 374 1712 211 1713 494 1714 793 1715 1100 1716 1410 1717 1715 1718 2016 1719 2305 1720 2589 1721 2868 1722 3134 1723 3387 1724 3634 1725 3861 1726 4081 1727 4288 1728 4481 1729 4667 1730 4833 1731 4985 1732 5129 1733 5253 1734 5365 1735 5462 1736 5546 1737 5617 1738 5671 1739 5711 1740 5740 1741 5750 1742 5748 1743 5732 1744 5698 1745 5649 1746 5595 1747 5513 1748 5425 1749 5324 1750 5204 1751 5071 1752 4932 1753 4771 1754 4595 1755 4409 1756 4213 1757 4001 1758 3777 1759 3540 1760 3296 1761 3031 1762 2765 1763 2483 1764 2196 1765 1900 1766 1598 1767 1291 1768 985 1769 678 1770 383 1771 216 1772 505 1773 812 1774 1123 1775 1440 1776 1754 1777 2059 1778 2358 1779 2649 1780 2933 1781 3207 1782 3468 1783 3718 1784 3960 1785 4189 1786 4399 1787 4602 1788 4792 1789 4968 1790 5131 1791 5273 1792 5409 1793 5534 1794 5632 1795 5727 1796 5803 1797 5870 1798 5914 1799 5947 1800 5969 1801 5972 1802 5962 1803 5936 1804 5897 1805 5844 1806 5779 1807 5692 1808 5599 1809 5485 1810 5362 1811 5220 1812 5067 1813 4900 1814 4722 1815 4529 1816 4323 1817 4100 1818 3868 1819 3628 1820 3369 1821 3103 1822 2831 1823 2543 1824 2247 1825 1940 1826 1632 1827 1318 1828 1005 1829 692 1830 391