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