1 1 2 2 3 4 4 3 5 6 6 9 7 5 8 8 9 12 10 16 11 7 12 11 13 15 14 20 15 25 16 10 17 14 18 19 19 24 20 30 21 37 22 13 23 18 24 23 25 29 26 35 27 43 28 51 29 17 30 22 31 28 32 34 33 41 34 49 35 58 36 67 37 21 38 27 39 33 40 40 41 47 42 56 43 65 44 75 45 85 46 26 47 32 48 39 49 46 50 54 51 63 52 73 53 83 54 94 55 106 56 31 57 38 58 45 59 53 60 61 61 71 62 81 63 92 64 103 65 116 66 129 67 36 68 44 69 52 70 60 71 69 72 79 73 90 74 101 75 113 76 126 77 140 78 154 79 42 80 50 81 59 82 68 83 77 84 88 85 99 86 111 87 123 88 137 89 151 90 166 91 181 92 48 93 57 94 66 95 76 96 86 97 97 98 109 99 121 100 134 101 148 102 163 103 178 104 194 105 211 106 55 107 64 108 74 109 84 110 95 111 107 112 119 113 132 114 145 115 160 116 175 117 191 118 207 119 225 120 243 121 62 122 72 123 82 124 93 125 104 126 117 127 130 128 143 129 157 130 172 131 188 132 204 133 221 134 239 135 258 136 277 137 70 138 80 139 91 140 102 141 114 142 127 143 141 144 155 145 169 146 185 147 201 148 218 149 235 150 254 151 273 152 293 153 313 154 78 155 89 156 100 157 112 158 124 159 138 160 152 161 167 162 182 163 198 164 215 165 232 166 250 167 269 168 289 169 309 170 330 171 352 172 87 173 98 174 110 175 122 176 135 177 149 178 164 179 179 180 195 181 212 182 229 183 247 184 265 185 285 186 305 187 326 188 347 189 370 190 393 191 96 192 108 193 120 194 133 195 146 196 161 197 176 198 192 199 208 200 226 201 244 202 262 203 281 204 301 205 322 206 343 207 365 208 388 209 412 210 436 211 105 212 118 213 131 214 144 215 158 216 173 217 189 218 205 219 222 220 240 221 259 222 278 223 297 224 318 225 339 226 361 227 383 228 407 229 431 230 456 231 481 232 115 233 128 234 142 235 156 236 170 237 186 238 202 239 219 240 236 241 255 242 274 243 294 244 314 245 335 246 357 247 379 248 402 249 426 250 451 251 476 252 502 253 528 254 125 255 139 256 153 257 168 258 183 259 199 260 216 261 233 262 251 263 270 264 290 265 310 266 331 267 353 268 375 269 398 270 421 271 446 272 471 273 497 274 523 275 550 276 578 277 136 278 150 279 165 280 180 281 196 282 213 283 230 284 248 285 266 286 286 287 306 288 327 289 348 290 371 291 394 292 417 293 441 294 466 295 492 296 518 297 545 298 572 299 601 300 630 301 147 302 162 303 177 304 193 305 209 306 227 307 245 308 263 309 282 310 302 311 323 312 344 313 366 314 389 315 413 316 437 317 461 318 487 319 513 320 540 321 567 322 595 323 624 324 654 325 684 326 159 327 174 328 190 329 206 330 223 331 241 332 260 333 279 334 298 335 319 336 340 337 362 338 384 339 408 340 432 341 457 342 482 343 508 344 535 345 562 346 590 347 618 348 648 349 678 350 709 351 740 352 171 353 187 354 203 355 220 356 237 357 256 358 275 359 295 360 315 361 336 362 358 363 380 364 403 365 427 366 452 367 477 368 503 369 530 370 557 371 585 372 613 373 642 374 672 375 703 376 734 377 766 378 799 379 184 380 200 381 217 382 234 383 252 384 271 385 291 386 311 387 332 388 354 389 376 390 399 391 422 392 447 393 472 394 498 395 524 396 552 397 580 398 608 399 637 400 666 401 697 402 728 403 760 404 792 405 826 406 860 407 197 408 214 409 231 410 249 411 267 412 287 413 307 414 328 415 349 416 372 417 395 418 418 419 442 420 467 421 493 422 519 423 546 424 574 425 603 426 632 427 661 428 691 429 722 430 754 431 786 432 819 433 853 434 888 435 923 436 210 437 228 438 246 439 264 440 283 441 303 442 324 443 345 444 367 445 390 446 414 447 438 448 462 449 488 450 514 451 541 452 568 453 597 454 626 455 656 456 686 457 716 458 748 459 780 460 813 461 846 462 881 463 916 464 952 465 988 466 224 467 242 468 261 469 280 470 299 471 320 472 341 473 363 474 385 475 409 476 433 477 458 478 483 479 509 480 536 481 563 482 591 483 620 484 650 485 680 486 711 487 742 488 774 489 807 490 840 491 874 492 909 493 945 494 981 495 1018 496 1056 497 238 498 257 499 276 500 296 501 316 502 337 503 359 504 381 505 404 506 428 507 453 508 478 509 504 510 531 511 558 512 586 513 614 514 644 515 674 516 705 517 736 518 768 519 801 520 834 521 868 522 902 523 938 524 974 525 1011 526 1048 527 1087 528 1126 529 253 530 272 531 292 532 312 533 333 534 355 535 377 536 400 537 423 538 448 539 473 540 499 541 525 542 553 543 581 544 609 545 638 546 668 547 699 548 730 549 762 550 794 551 828 552 862 553 896 554 931 555 967 556 1004 557 1041 558 1079 559 1118 560 1158 561 1198 562 268 563 288 564 308 565 329 566 350 567 373 568 396 569 419 570 443 571 468 572 494 573 520 574 547 575 575 576 604 577 633 578 662 579 693 580 724 581 756 582 788 583 821 584 855 585 890 586 925 587 960 588 997 589 1034 590 1072 591 1110 592 1150 593 1190 594 1231 595 1272 596 284 597 304 598 325 599 346 600 368 601 391 602 415 603 439 604 463 605 489 606 515 607 542 608 569 609 598 610 627 611 657 612 687 613 718 614 750 615 782 616 815 617 848 618 883 619 918 620 954 621 990 622 1027 623 1065 624 1103 625 1142 626 1182 627 1223 628 1264 629 1306 630 1349 631 300 632 321 633 342 634 364 635 386 636 410 637 434 638 459 639 484 640 510 641 537 642 564 643 592 644 621 645 651 646 681 647 712 648 744 649 776 650 809 651 842 652 876 653 911 654 947 655 983 656 1020 657 1058 658 1096 659 1135 660 1174 661 1215 662 1256 663 1298 664 1340 665 1384 666 1428 667 317 668 338 669 360 670 382 671 405 672 429 673 454 674 479 675 505 676 532 677 559 678 587 679 615 680 645 681 675 682 706 683 737 684 770 685 803 686 836 687 870 688 904 689 940 690 976 691 1013 692 1050 693 1089 694 1128 695 1167 696 1207 697 1248 698 1290 699 1332 700 1375 701 1419 702 1464 703 1509 704 334 705 356 706 378 707 401 708 424 709 449 710 474 711 500 712 526 713 554 714 582 715 610 716 639 717 669 718 700 719 731 720 763 721 796 722 830 723 864 724 898 725 933 726 969 727 1006 728 1043 729 1081 730 1120 731 1160 732 1200 733 1240 734 1282 735 1324 736 1367 737 1410 738 1455 739 1500 740 1546 741 1592 742 351 743 374 744 397 745 420 746 444 747 469 748 495 749 521 750 548 751 576 752 605 753 634 754 663 755 694 756 725 757 757 758 789 759 823 760 857 761 892 762 927 763 962 764 999 765 1036 766 1074 767 1112 768 1152 769 1192 770 1233 771 1274 772 1316 773 1359 774 1402 775 1446 776 1491 777 1537 778 1583 779 1630 780 1677 781 369 782 392 783 416 784 440 785 464 786 490 787 516 788 543 789 570 790 599 791 628 792 658 793 688 794 719 795 751 796 783 797 816 798 850 799 885 800 920 801 956 802 992 803 1029 804 1067 805 1105 806 1144 807 1184 808 1225 809 1266 810 1308 811 1351 812 1394 813 1438 814 1482 815 1528 816 1574 817 1621 818 1668 819 1716 820 1765 821 387 822 411 823 435 824 460 825 485 826 511 827 538 828 565 829 593 830 622 831 652 832 682 833 713 834 745 835 777 836 810 837 843 838 878 839 913 840 949 841 985 842 1022 843 1060 844 1098 845 1137 846 1176 847 1217 848 1258 849 1300 850 1342 851 1386 852 1430 853 1474 854 1519 855 1565 856 1612 857 1659 858 1707 859 1755 860 1805 861 1855 862 406 863 430 864 455 865 480 866 506 867 533 868 560 869 588 870 616 871 646 872 676 873 707 874 738 875 771 876 804 877 837 878 871 879 906 880 942 881 978 882 1015 883 1052 884 1091 885 1130 886 1169 887 1209 888 1250 889 1292 890 1334 891 1377 892 1421 893 1466 894 1511 895 1556 896 1603 897 1650 898 1698 899 1746 900 1795 901 1845 902 1896 903 1947 904 425 905 450 906 475 907 501 908 527 909 555 910 583 911 611 912 640 913 670 914 701 915 732 916 764 917 797 918 831 919 865 920 899 921 935 922 971 923 1008 924 1045 925 1083 926 1122 927 1162 928 1202 929 1242 930 1284 931 1326 932 1369 933 1412 934 1457 935 1502 936 1548 937 1594 938 1641 939 1689 940 1737 941 1786 942 1835 943 1886 944 1937 945 1989 946 2041 947 445 948 470 949 496 950 522 951 549 952 577 953 606 954 635 955 664 956 695 957 726 958 758 959 790 960 824 961 858 962 893 963 928 964 964 965 1001 966 1038 967 1076 968 1114 969 1154 970 1194 971 1235 972 1276 973 1318 974 1361 975 1404 976 1448 977 1493 978 1539 979 1585 980 1632 981 1680 982 1728 983 1777 984 1826 985 1876 986 1927 987 1979 988 2031 989 2084 990 2138 991 465 992 491 993 517 994 544 995 571 996 600 997 629 998 659 999 689 1000 720 1001 752 1002 784 1003 817 1004 851 1005 886 1006 921 1007 957 1008 994 1009 1031 1010 1069 1011 1107 1012 1146 1013 1186 1014 1227 1015 1268 1016 1310 1017 1353 1018 1396 1019 1440 1020 1484 1021 1530 1022 1576 1023 1623 1024 1670 1025 1719 1026 1768 1027 1817 1028 1867 1029 1917 1030 1969 1031 2021 1032 2074 1033 2127 1034 2182 1035 2237 1036 486 1037 512 1038 539 1039 566 1040 594 1041 623 1042 653 1043 683 1044 714 1045 746 1046 778 1047 811 1048 844 1049 879 1050 914 1051 950 1052 986 1053 1024 1054 1062 1055 1100 1056 1139 1057 1178 1058 1219 1059 1260 1060 1302 1061 1344 1062 1388 1063 1432 1064 1476 1065 1521 1066 1567 1067 1614 1068 1661 1069 1709 1070 1758 1071 1808 1072 1858 1073 1908 1074 1959 1075 2011 1076 2064 1077 2117 1078 2171 1079 2226 1080 2282 1081 2338 1082 507 1083 534 1084 561 1085 589 1086 617 1087 647 1088 677 1089 708 1090 739 1091 772 1092 805 1093 838 1094 872 1095 907 1096 943 1097 979 1098 1016 1099 1054 1100 1093 1101 1132 1102 1171 1103 1211 1104 1252 1105 1294 1106 1336 1107 1379 1108 1423 1109 1468 1110 1513 1111 1558 1112 1605 1113 1652 1114 1700 1115 1748 1116 1798 1117 1848 1118 1899 1119 1950 1120 2001 1121 2054 1122 2107 1123 2161 1124 2215 1125 2271 1126 2327 1127 2384 1128 2441 1129 529 1130 556 1131 584 1132 612 1133 641 1134 671 1135 702 1136 733 1137 765 1138 798 1139 832 1140 866 1141 900 1142 936 1143 972 1144 1009 1145 1046 1146 1085 1147 1124 1148 1164 1149 1204 1150 1244 1151 1286 1152 1328 1153 1371 1154 1414 1155 1459 1156 1504 1157 1550 1158 1596 1159 1643 1160 1691 1161 1739 1162 1788 1163 1838 1164 1889 1165 1940 1166 1992 1167 2044 1168 2097 1169 2151 1170 2205 1171 2260 1172 2316 1173 2373 1174 2430 1175 2488 1176 2547 1177 551 1178 579 1179 607 1180 636 1181 665 1182 696 1183 727 1184 759 1185 791 1186 825 1187 859 1188 894 1189 929 1190 965 1191 1002 1192 1039 1193 1077 1194 1116 1195 1156 1196 1196 1197 1237 1198 1278 1199 1320 1200 1363 1201 1406 1202 1450 1203 1495 1204 1541 1205 1587 1206 1634 1207 1682 1208 1730 1209 1779 1210 1828 1211 1879 1212 1930 1213 1982 1214 2034 1215 2087 1216 2141 1217 2195 1218 2250 1219 2305 1220 2362 1221 2419 1222 2477 1223 2535 1224 2595 1225 2655 1226 573 1227 602 1228 631 1229 660 1230 690 1231 721 1232 753 1233 785 1234 818 1235 852 1236 887 1237 922 1238 958 1239 995 1240 1032 1241 1070 1242 1108 1243 1148 1244 1188 1245 1229 1246 1270 1247 1312 1248 1355 1249 1398 1250 1442 1251 1486 1252 1532 1253 1578 1254 1625 1255 1672 1256 1721 1257 1770 1258 1819 1259 1869 1260 1920 1261 1972 1262 2024 1263 2077 1264 2130 1265 2185 1266 2240 1267 2295 1268 2351 1269 2408 1270 2466 1271 2524 1272 2583 1273 2643 1274 2704 1275 2765 1276 596 1277 625 1278 655 1279 685 1280 715 1281 747 1282 779 1283 812 1284 845 1285 880 1286 915 1287 951 1288 987 1289 1025 1290 1063 1291 1101 1292 1140 1293 1180 1294 1221 1295 1262 1296 1304 1297 1346 1298 1390 1299 1434 1300 1478 1301 1523 1302 1569 1303 1616 1304 1663 1305 1711 1306 1760 1307 1810 1308 1860 1309 1910 1310 1962 1311 2014 1312 2067 1313 2120 1314 2174 1315 2229 1316 2285 1317 2341 1318 2397 1319 2455 1320 2513 1321 2572 1322 2631 1323 2692 1324 2753 1325 2815 1326 2877 1327 619 1328 649 1329 679 1330 710 1331 741 1332 773 1333 806 1334 839 1335 873 1336 908 1337 944 1338 980 1339 1017 1340 1055 1341 1094 1342 1133 1343 1172 1344 1213 1345 1254 1346 1296 1347 1338 1348 1381 1349 1425 1350 1470 1351 1515 1352 1560 1353 1607 1354 1654 1355 1702 1356 1750 1357 1800 1358 1850 1359 1901 1360 1952 1361 2004 1362 2057 1363 2110 1364 2164 1365 2218 1366 2274 1367 2330 1368 2387 1369 2444 1370 2502 1371 2561 1372 2620 1373 2680 1374 2741 1375 2803 1376 2865 1377 2928 1378 2992 1379 643 1380 673 1381 704 1382 735 1383 767 1384 800 1385 833 1386 867 1387 901 1388 937 1389 973 1390 1010 1391 1047 1392 1086 1393 1125 1394 1165 1395 1205 1396 1246 1397 1288 1398 1330 1399 1373 1400 1416 1401 1461 1402 1506 1403 1552 1404 1598 1405 1645 1406 1693 1407 1741 1408 1790 1409 1840 1410 1891 1411 1942 1412 1994 1413 2047 1414 2100 1415 2154 1416 2208 1417 2263 1418 2319 1419 2376 1420 2433 1421 2491 1422 2550 1423 2609 1424 2669 1425 2729 1426 2791 1427 2853 1428 2916 1429 2979 1430 3044 1431 3109 1432 667 1433 698 1434 729 1435 761 1436 793 1437 827 1438 861 1439 895 1440 930 1441 966 1442 1003 1443 1040 1444 1078 1445 1117 1446 1157 1447 1197 1448 1238 1449 1280 1450 1322 1451 1365 1452 1408 1453 1452 1454 1497 1455 1543 1456 1589 1457 1636 1458 1684 1459 1732 1460 1781 1461 1830 1462 1881 1463 1932 1464 1984 1465 2036 1466 2090 1467 2144 1468 2198 1469 2253 1470 2308 1471 2365 1472 2422 1473 2480 1474 2538 1475 2598 1476 2658 1477 2718 1478 2779 1479 2841 1480 2904 1481 2967 1482 3031 1483 3096 1484 3162 1485 3228 1486 692 1487 723 1488 755 1489 787 1490 820 1491 854 1492 889 1493 924 1494 959 1495 996 1496 1033 1497 1071 1498 1109 1499 1149 1500 1189 1501 1230 1502 1271 1503 1314 1504 1357 1505 1400 1506 1444 1507 1488 1508 1534 1509 1580 1510 1627 1511 1674 1512 1723 1513 1772 1514 1821 1515 1871 1516 1922 1517 1974 1518 2026 1519 2079 1520 2133 1521 2188 1522 2243 1523 2298 1524 2354 1525 2411 1526 2469 1527 2527 1528 2586 1529 2646 1530 2707 1531 2768 1532 2829 1533 2892 1534 2955 1535 3019 1536 3083 1537 3149 1538 3215 1539 3282 1540 3349 1541 717 1542 749 1543 781 1544 814 1545 847 1546 882 1547 917 1548 953 1549 989 1550 1026 1551 1064 1552 1102 1553 1141 1554 1181 1555 1222 1556 1263 1557 1305 1558 1348 1559 1392 1560 1436 1561 1480 1562 1525 1563 1571 1564 1618 1565 1665 1566 1713 1567 1762 1568 1812 1569 1862 1570 1912 1571 1964 1572 2016 1573 2069 1574 2122 1575 2177 1576 2232 1577 2288 1578 2344 1579 2400 1580 2458 1581 2516 1582 2575 1583 2634 1584 2695 1585 2756 1586 2818 1587 2880 1588 2943 1589 3007 1590 3071 1591 3136 1592 3202 1593 3269 1594 3336 1595 3404 1596 3472 1597 743 1598 775 1599 808 1600 841 1601 875 1602 910 1603 946 1604 982 1605 1019 1606 1057 1607 1095 1608 1134 1609 1173 1610 1214 1611 1255 1612 1297 1613 1339 1614 1383 1615 1427 1616 1472 1617 1517 1618 1562 1619 1609 1620 1656 1621 1704 1622 1752 1623 1802 1624 1852 1625 1903 1626 1954 1627 2006 1628 2059 1629 2112 1630 2166 1631 2221 1632 2277 1633 2333 1634 2390 1635 2447 1636 2505 1637 2564 1638 2623 1639 2683 1640 2744 1641 2806 1642 2868 1643 2931 1644 2995 1645 3059 1646 3124 1647 3189 1648 3256 1649 3323 1650 3391 1651 3459 1652 3528 1653 3598 1654 769 1655 802 1656 835 1657 869 1658 903 1659 939 1660 975 1661 1012 1662 1049 1663 1088 1664 1127 1665 1166 1666 1206 1667 1247 1668 1289 1669 1331 1670 1374 1671 1418 1672 1463 1673 1508 1674 1554 1675 1600 1676 1647 1677 1695 1678 1743 1679 1792 1680 1842 1681 1893 1682 1944 1683 1996 1684 2049 1685 2102 1686 2156 1687 2210 1688 2266 1689 2322 1690 2379 1691 2436 1692 2494 1693 2553 1694 2612 1695 2672 1696 2732 1697 2794 1698 2856 1699 2919 1700 2982 1701 3047 1702 3112 1703 3177 1704 3243 1705 3310 1706 3378 1707 3446 1708 3515 1709 3584 1710 3655 1711 3726 1712 795 1713 829 1714 863 1715 897 1716 932 1717 968 1718 1005 1719 1042 1720 1080 1721 1119 1722 1159 1723 1199 1724 1239 1725 1281 1726 1323 1727 1366 1728 1409 1729 1454 1730 1499 1731 1545 1732 1591 1733 1638 1734 1686 1735 1734 1736 1783 1737 1832 1738 1883 1739 1934 1740 1986 1741 2038 1742 2092 1743 2146 1744 2200 1745 2255 1746 2311 1747 2368 1748 2425 1749 2483 1750 2541 1751 2601 1752 2661 1753 2721 1754 2782 1755 2844 1756 2907 1757 2970 1758 3034 1759 3099 1760 3165 1761 3231 1762 3297 1763 3365 1764 3433 1765 3502 1766 3571 1767 3641 1768 3712 1769 3784 1770 3856 1771 822 1772 856 1773 891 1774 926 1775 961 1776 998 1777 1035 1778 1073 1779 1111 1780 1151 1781 1191 1782 1232 1783 1273 1784 1315 1785 1358 1786 1401 1787 1445 1788 1490 1789 1536 1790 1582 1791 1629 1792 1676 1793 1725 1794 1774 1795 1823 1796 1873 1797 1924 1798 1976 1799 2028 1800 2081 1801 2135 1802 2190 1803 2245 1804 2300 1805 2357 1806 2414 1807 2472 1808 2530 1809 2589 1810 2649 1811 2710 1812 2771 1813 2832 1814 2895 1815 2958 1816 3022 1817 3086 1818 3152 1819 3218 1820 3285 1821 3352 1822 3420 1823 3489 1824 3558 1825 3628 1826 3698 1827 3770 1828 3842 1829 3915 1830 3988