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