0 1 2 2 3 0 4 5 6 6 7 4 8 9 10 10 11 8 12 13 14 14 15 12 16 17 18 18 19 16 20 21 22 22 23 20 24 25 26 26 27 24 28 29 30 30 31 28 32 33 34 34 35 32 36 37 38 38 39 36 40 41 42 42 43 40 44 45 46 46 47 44 48 49 50 50 51 48 52 53 54 54 55 52 56 57 58 59 60 61 62 63 64 64 65 62 66 67 68 66 68 69 70 66 69 71 72 73 74 71 73 73 75 74 76 77 78 78 79 76 80 81 82 82 83 80 84 85 86 86 87 84 88 89 90 90 91 88 92 93 94 94 93 95 95 93 96 97 98 99 99 100 97 101 102 103 103 104 101 105 106 107 107 108 105 109 110 111 111 112 109 113 114 115 115 116 113 117 118 119 119 120 117 121 122 123 123 124 121 125 126 127 127 128 125 129 130 131 131 132 129 133 134 135 135 136 133 137 138 139 139 140 137 141 142 143 143 144 141 145 146 147 147 148 145 149 150 151 151 152 149 153 154 155 155 156 153 157 158 159 159 160 157 161 162 163 163 164 161 165 166 167 167 168 165 169 170 171 171 172 169 173 174 175 175 176 173 177 178 179 179 180 177 181 182 183 183 182 184 184 182 185 186 187 188 188 189 186 190 191 192 192 193 190 194 195 196 196 197 194 198 199 200 200 201 198 202 203 204 204 205 202 206 207 208 208 209 206 210 211 212 212 213 210 214 215 216 216 217 214 218 219 220 220 221 218 222 223 224 224 225 222 226 227 228 228 229 226 230 231 232 232 233 230 234 235 236 236 237 234 238 239 240 240 241 238 242 243 244 244 245 242 246 247 248 248 249 246 250 251 252 252 253 250 254 255 256 256 257 254 258 259 260 260 261 258 262 263 264 264 265 262 266 267 268 268 269 266 270 271 272 272 273 270 274 275 276 276 277 274 278 279 280 280 281 278 282 283 284 284 285 282 286 287 288 288 289 286 290 291 292 292 293 290 294 295 296 296 297 294 298 299 300 300 301 298 302 303 304 304 305 302 306 307 308 308 309 306 310 311 312 312 313 310 314 315 316 316 317 314 318 319 320 320 321 318 322 323 324 324 325 322 326 327 328 328 329 326 330 331 332 332 333 330 334 335 336 336 337 334 338 339 340 340 341 338 342 343 344 344 345 342 346 347 348 348 349 346 350 351 352 352 353 350 354 355 356 356 357 354 358 359 360 360 361 358 362 363 364 364 365 362 366 367 368 368 369 366 370 371 372 372 373 370 374 375 376 377 378 379 380 381 382 382 383 380 384 385 386 387 388 389 390 391 392 392 393 390 394 395 396 397 398 399 400 401 402 402 403 400 377 404 405 379 404 377 374 406 407 376 406 374 387 408 409 389 408 387 384 410 411 386 410 384 397 412 413 399 412 397 394 414 415 396 414 394 416 417 418 418 419 416 417 420 421 421 418 417 422 423 424 424 425 422 423 426 427 427 424 423 426 428 429 429 427 426 430 416 419 419 431 430 432 433 434 434 435 432 436 437 438 438 439 436 440 441 442 442 443 440 444 445 446 446 447 444 448 449 450 450 451 448 452 453 454 454 455 452 456 457 458 458 459 456 460 461 462 462 463 460 464 465 466 466 467 464 465 468 469 469 466 465 470 471 472 472 473 470 471 474 475 475 472 471 474 476 477 477 475 474 478 464 467 467 479 478 480 481 482 482 483 480 484 485 486 486 487 484 488 489 490 490 491 488 492 493 494 494 495 492 496 497 498 498 499 496 497 500 501 501 498 497 502 503 504 504 505 502 503 506 507 507 504 503 506 508 509 509 507 506 510 496 499 499 511 510 512 513 514 514 515 512 513 516 517 517 514 513 518 519 520 520 521 518 519 522 523 523 520 519 522 524 525 525 523 522 526 512 515 515 527 526 528 529 530 530 531 528 529 532 533 533 530 529 534 535 536 536 537 534 538 539 540 540 541 538 539 542 543 543 540 539 544 528 531 531 545 544 546 547 548 548 549 546 550 551 552 552 553 550 554 555 556 556 557 554 558 559 560 560 561 558 562 563 564 564 565 562 563 566 567 567 564 563 568 569 570 570 571 568 569 572 573 573 570 569 572 574 575 575 573 572 576 562 565 565 577 576 578 579 580 580 581 578 579 582 583 583 580 579 584 585 586 586 587 584 585 588 589 589 586 585 588 590 591 591 589 588 592 578 581 581 593 592 594 595 596 596 597 594 598 599 600 600 601 598 602 603 604 604 605 602 606 607 608 608 609 606 610 611 612 612 613 610 614 615 616 616 617 614 618 619 620 620 621 618 622 623 624 624 625 622 626 627 628 628 629 626 627 630 631 631 628 627 632 633 634 634 635 632 633 636 637 637 634 633 636 638 639 639 637 636 640 626 629 629 641 640 642 643 644 644 645 642 646 647 648 648 649 646 650 651 652 652 653 650 654 655 656 656 657 654 658 659 660 660 661 658 659 662 663 663 660 659 664 665 666 666 667 664 665 668 669 669 666 665 668 670 671 671 669 668 672 658 661 661 673 672 674 675 676 676 677 674 678 679 680 680 681 678 682 683 684 684 685 682 686 687 688 688 689 686 690 691 692 692 693 690 691 694 695 695 692 691 696 697 698 698 699 696 697 700 701 701 698 697 700 702 703 703 701 700 704 690 693 693 705 704 706 707 708 708 709 706 710 711 712 712 713 710 714 715 716 716 717 714 718 719 720 720 721 718 722 723 724 724 725 722 726 727 728 728 729 726 730 731 732 732 733 730 734 735 736 736 737 734 738 739 740 740 741 738 739 742 743 743 740 739 744 745 746 746 747 744 745 748 749 749 746 745 748 750 751 751 749 748 752 738 741 741 753 752 754 755 756 756 757 754 758 759 760 760 761 758 762 763 764 764 765 762 766 767 768 768 769 766 770 771 772 772 773 770 771 774 775 775 772 771 776 777 778 778 779 776 777 780 781 781 778 777 780 782 783 783 781 780 784 770 773 773 785 784 786 787 788 788 789 786 790 791 792 792 793 790 794 795 796 796 797 794 798 799 800 800 801 798 802 803 804 804 805 802 803 806 807 807 804 803 808 809 810 810 811 808 809 812 813 813 810 809 812 814 815 815 813 812 816 802 805 805 817 816 818 819 820 820 821 818 822 823 824 824 825 822 826 827 828 828 829 826 830 831 832 832 833 830 834 835 836 836 837 834 835 838 839 839 836 835 840 841 842 842 843 840 841 844 845 845 842 841 844 846 847 847 845 844 848 834 837 837 849 848 850 851 852 852 853 850 854 855 856 856 857 854 858 859 860 860 861 858 862 863 864 864 865 862 866 867 868 869 870 871 871 872 869 873 874 875 875 876 873 877 878 879 880 881 882 883 884 885 885 886 883 887 888 889 889 890 887 891 892 893 893 894 891 888 895 896 896 889 888 897 898 899 899 900 897 901 902 903 901 904 902 904 905 902 904 906 905 906 907 905 906 908 907 909 910 911 909 912 910 912 913 910 912 914 913 914 915 913 914 916 915 916 917 915 916 918 917 919 920 921 919 922 920 922 923 920 922 924 923 924 925 923 924 926 925 926 927 925 926 928 927 929 930 931 929 932 930 932 933 930 932 934 933 934 935 933 934 936 935 936 937 935 936 938 937 939 940 941 939 942 940 942 943 940 942 944 943 944 945 943 944 946 945 947 948 949 947 949 950 947 950 951 947 951 952 947 952 953 947 953 954 947 954 955 947 955 956 947 956 957 947 957 958 947 958 959 947 959 960 947 960 961 947 961 962 947 962 963 947 964 965 947 965 966 947 966 948 967 968 969 969 970 967 971 972 973 971 973 974 974 973 975 974 975 976 976 975 977 976 977 978 978 977 979 978 979 980 980 979 981 980 981 982 982 981 983 982 983 984 984 983 985 984 985 986 986 985 987 986 987 988 988 987 989 988 989 990 991 992 993 991 993 994 994 993 995 994 995 996 996 995 997 996 997 998 998 997 999 998 999 1000 1000 999 1001 1000 1001 1002 1002 1001 1003 1002 1003 1004 1004 1003 1005 1004 1005 1006 1006 1005 1007 1006 1007 1008 1008 1007 1009 1008 1009 1010 972 1011 1012 972 1012 973 973 1012 1013 973 1013 975 975 1013 1014 975 1014 977 977 1014 1015 977 1015 979 979 1015 1016 979 1016 981 981 1016 1017 981 1017 983 983 1017 1018 983 1018 985 985 1018 1019 985 1019 987 987 1019 1020 987 1020 989 992 1021 1022 992 1022 993 993 1022 1023 993 1023 995 995 1023 1024 995 1024 997 997 1024 1025 997 1025 999 999 1025 1026 999 1026 1001 1001 1026 1027 1001 1027 1003 1003 1027 1028 1003 1028 1005 1005 1028 1029 1005 1029 1007 1007 1029 1030 1007 1030 1009 1011 1031 1032 1011 1032 1012 1012 1032 1033 1012 1033 1013 1013 1033 1034 1013 1034 1014 1014 1034 1035 1014 1035 1015 1015 1035 1036 1015 1036 1016 1016 1036 1037 1016 1037 1017 1017 1037 1038 1017 1038 1018 1018 1038 1039 1018 1039 1019 1019 1039 1040 1019 1040 1020 1021 1041 1042 1021 1042 1022 1022 1042 1043 1022 1043 1023 1023 1043 1044 1023 1044 1024 1024 1044 1045 1024 1045 1025 1025 1045 1046 1025 1046 1026 1026 1046 1047 1026 1047 1027 1027 1047 1048 1027 1048 1028 1028 1048 1049 1028 1049 1029 1029 1049 1050 1029 1050 1030 1051 1052 1053 1051 1053 1054 1054 1053 1055 1054 1055 1056 1056 1055 1057 1056 1057 1058 1058 1057 1059 1058 1059 1060 1060 1059 1061 1060 1061 1062 1062 1061 1063 1062 1063 1064 1064 1063 1065 1064 1065 1066 1066 1065 1067 1066 1067 1068 1068 1067 1069 1068 1069 1070 1071 1072 1073 1071 1073 1074 1074 1073 1075 1074 1075 1076 1076 1075 1077 1076 1077 1078 1078 1077 1079 1078 1079 1080 1080 1079 1081 1080 1081 1082 1082 1081 1083 1082 1083 1084 1084 1083 1085 1084 1085 1086 1086 1085 1087 1086 1087 1088 1088 1087 1089 1088 1089 1090 1052 1091 1092 1052 1092 1053 1053 1092 1093 1053 1093 1055 1055 1093 1094 1055 1094 1057 1057 1094 1095 1057 1095 1059 1059 1095 1096 1059 1096 1061 1061 1096 1097 1061 1097 1063 1063 1097 1098 1063 1098 1065 1065 1098 1099 1065 1099 1067 1067 1099 1100 1067 1100 1069 1072 1101 1102 1072 1102 1073 1073 1102 1103 1073 1103 1075 1075 1103 1104 1075 1104 1077 1077 1104 1105 1077 1105 1079 1079 1105 1106 1079 1106 1081 1081 1106 1107 1081 1107 1083 1083 1107 1108 1083 1108 1085 1085 1108 1109 1085 1109 1087 1087 1109 1110 1087 1110 1089 1091 1111 1112 1091 1112 1092 1092 1112 1113 1092 1113 1093 1093 1113 1114 1093 1114 1094 1094 1114 1115 1094 1115 1095 1095 1115 1116 1095 1116 1096 1096 1116 1117 1096 1117 1097 1097 1117 1118 1097 1118 1098 1098 1118 1119 1098 1119 1099 1099 1119 1120 1099 1120 1100 1101 1121 1122 1101 1122 1102 1102 1122 1123 1102 1123 1103 1103 1123 1124 1103 1124 1104 1104 1124 1125 1104 1125 1105 1105 1125 1126 1105 1126 1106 1106 1126 1127 1106 1127 1107 1107 1127 1128 1107 1128 1108 1108 1128 1129 1108 1129 1109 1109 1129 1130 1109 1130 1110 1131 1132 1133 1133 1134 1131 1132 1135 1136 1136 1133 1132 1135 1137 1138 1138 1136 1135 1139 1140 1141 1141 1142 1139 1140 1143 1144 1144 1141 1140 1143 1145 1146 1146 1144 1143 1147 1148 1149 1149 1150 1147 1148 1151 1152 1152 1149 1148 1151 1153 1154 1154 1152 1151 1155 1156 1157 1157 1158 1155 1156 1159 1160 1160 1157 1156 1159 1161 1162 1162 1160 1159 1163 1164 1165 1165 1166 1163 1164 1167 1168 1168 1165 1164 1167 1169 1170 1170 1168 1167 1171 1172 1173 1173 1174 1171 1172 1175 1176 1176 1173 1172 1177 1178 1179 1179 1180 1177 1178 1181 1182 1182 1179 1178 1183 1184 1185 1183 1185 1186 1187 1188 1189 1189 1190 1191 1187 1189 1191 1192 1193 1194 1195 1192 1194 1196 1197 1198 1199 1196 1198 1200 1201 1202 1203 1200 1202 1204 1205 1206 1207 1204 1206 1208 1209 1210 1211 1208 1210 1212 1213 1214 1215 1212 1214 1216 1217 1218 1216 1218 1219 1220 1221 1222 1223 1220 1222 1224 1225 1226 1227 1224 1226 1228 1229 1230 1231 1228 1230 1232 1233 1234 1235 1232 1234 1236 1237 1238 1185 1184 1239 1240 1241 1242 1243 1240 1242 1236 1238 1244 1245 1246 1247 1245 1248 1246 1249 1250 1251 1249 1252 1250 1253 1254 1255 1253 1256 1254 1247 1257 1258 1247 1246 1257 1251 1259 1260 1251 1250 1259 1255 1261 1262 1255 1254 1261 1258 1263 1264 1258 1257 1263 1260 1265 1266 1260 1259 1265 1262 1267 1268 1262 1261 1267 1264 1269 1270 1264 1263 1269 1266 1271 1272 1266 1265 1271 1268 1273 1274 1268 1267 1273 1270 1275 1276 1270 1269 1275 1277 1278 1279 1277 1280 1278 1274 1281 1282 1274 1273 1281 1283 1284 1285 1283 1286 1284 1279 1287 1288 1279 1278 1287 1289 1290 1291 1289 1292 1290 1285 1293 1294 1285 1284 1293 1288 1295 1296 1288 1287 1295 1291 1297 1298 1291 1290 1297 1294 1299 1300 1294 1293 1299 1296 1301 1302 1296 1295 1301 1298 1303 1304 1298 1297 1303 1300 1305 1306 1300 1299 1305 1302 1307 1308 1302 1301 1307 1304 1309 1310 1304 1303 1309 1311 1312 1313 1311 1314 1312 1315 1316 1317 1315 1318 1316 1319 1320 1321 1319 1322 1320 1313 1323 1324 1313 1312 1323 1317 1325 1326 1317 1316 1325 1321 1327 1328 1321 1320 1327 1324 1329 1330 1324 1323 1329 1326 1331 1332 1326 1325 1331 1328 1333 1334 1328 1327 1333 1330 1335 1336 1330 1329 1335 1332 1337 1338 1332 1331 1337 1334 1339 1340 1334 1333 1339 1336 1341 1342 1336 1335 1341 1338 1343 1344 1338 1337 1343 1340 1345 1346 1340 1339 1345 1347 1348 1349 1347 1349 1350 1350 1349 1351 1350 1351 1352 1352 1351 1353 1352 1353 1354 1354 1353 1355 1354 1355 1356 1356 1355 1357 1356 1357 1358 1358 1357 1359 1358 1359 1360 1360 1359 1361 1360 1361 1362 1362 1361 1363 1362 1363 1364 1364 1363 1365 1364 1365 1366 1367 1368 1369 1367 1369 1370 1370 1369 1371 1370 1371 1372 1372 1371 1373 1372 1373 1374 1374 1373 1375 1374 1375 1376 1376 1375 1377 1376 1377 1378 1378 1377 1379 1378 1379 1380 1380 1379 1381 1380 1381 1382 1382 1381 1383 1382 1383 1384 1384 1383 1385 1384 1385 1386 1348 1387 1388 1348 1388 1349 1349 1388 1389 1349 1389 1351 1351 1389 1390 1351 1390 1353 1353 1390 1391 1353 1391 1355 1355 1391 1392 1355 1392 1357 1357 1392 1393 1357 1393 1359 1359 1393 1394 1359 1394 1361 1361 1394 1395 1361 1395 1363 1363 1395 1396 1363 1396 1365 1368 1397 1398 1368 1398 1369 1369 1398 1399 1369 1399 1371 1371 1399 1400 1371 1400 1373 1373 1400 1401 1373 1401 1375 1375 1401 1402 1375 1402 1377 1377 1402 1403 1377 1403 1379 1379 1403 1404 1379 1404 1381 1381 1404 1405 1381 1405 1383 1383 1405 1406 1383 1406 1385 1387 1407 1408 1387 1408 1388 1388 1408 1409 1388 1409 1389 1389 1409 1410 1389 1410 1390 1390 1410 1411 1390 1411 1391 1391 1411 1412 1391 1412 1392 1392 1412 1413 1392 1413 1393 1393 1413 1414 1393 1414 1394 1394 1414 1415 1394 1415 1395 1395 1415 1416 1395 1416 1396 1397 1417 1418 1397 1418 1398 1398 1418 1419 1398 1419 1399 1399 1419 1420 1399 1420 1400 1400 1420 1421 1400 1421 1401 1401 1421 1422 1401 1422 1402 1402 1422 1423 1402 1423 1403 1403 1423 1424 1403 1424 1404 1404 1424 1425 1404 1425 1405 1405 1425 1426 1405 1426 1406 1427 1428 1429 1429 1430 1427 1431 1432 1433 1434 1433 1432 1435 1436 1437 1435 1438 1436 1439 1440 1441 1439 1442 1440 1443 1444 1445 1443 1446 1444 1447 1448 1449 1447 1450 1448 1451 1452 1453 1451 1454 1452 1455 1456 1457 1455 1458 1456 1459 1460 1461 1459 1462 1460 1463 1464 1465 1463 1466 1464 1467 1468 1469 1467 1470 1468 1471 1472 1473 1471 1474 1472 1475 1476 1477 1475 1478 1476 1479 1480 1481 1479 1482 1480 1483 1484 1485 1483 1486 1484 1487 1488 1489 1487 1490 1488 1491 1492 1493 1491 1494 1492 1495 1496 1497 1495 1498 1496 1499 1500 1501 1499 1502 1500 1503 1504 1505 1503 1506 1504 1507 1508 1509 1510 1509 1508 1511 1512 1513 1514 1513 1512