3998 7
0 1 2 3 2 4 1 4 3 5 8 6 4 12 2 5 12 11 12 17 9 4 17 1 5 21 4 16 3 9 22 8 25 26 30 19 30 9 16 5 19 29 3 22 34 35 9 32 40 7 30 34 42 10 28 12 9 25 7 3 45 8 26 34 6 7 18 37 55 63 45 11 56 47 66 23 67 74 20 22 4 21 82 58 12 65 35 63 55 21 84 21 29 63 93 67 19 10 10 31 99 56 82 59 39 9 21 25 6 20 55 41 100 84 41 89 5 32 99 6 88 101 37 15 94 63 13 87 75 38 74 19 119 82 5 81 19 117 48 57 7 134 70 3 123 1 30 69 111 48 135 101 118 135 113 50 31 104 39 143 61 71 88 90 113 92 157 112 157 93 86 156 154 152 163 134 91 167 143 111 124 117 3 73 34 96 108 149 127 78 7 9 47 12 99 31 122 89 141 30 169 122 120 136 111 165 147 70 175 97 61 208 9 79 78 24 207 130 106 26 103 132 13 68 212 127 32 91 224 117 212 77 187 76 144 195 44 199 115 92 222 59 58 227 220 99 149 218 239 52 95 140 136 70 78 19 187 33 35 163 200 110 129 257 105 91 239 125 63 147 112 101 253 211 84 197 167 248 86 264 223 174 202 240 243 215 126 46 6 261 172 129 173 2 59 60 7 203 55 107 13 182 209 179 262 135 122 30 132 57 7 238 300 161 61 129 31 34 45 272 214 231 198 9 171 295 203 175 44 142 183 207 60 328 160 202 243 73 191 144 80 334 200 94 48 124 225 315 137 67 81 17 35 196 32 60 266 167 20 192 56 265 360 197 38 75 179 160 175 137 198 355 175 270 77 193 41 52 115 295 328 107 345 173 217 129 48 145 174 9 352 73 265 347 225 158 284 192 324 101 150 229 7 322 334 35 151 237 307 81 101 390 299 109 18 229 24 364 384 18 395 296 286 81 236 284 91 186 364 414 30 419 383 359 274 56 315 232 253 191 187 17 185 441 149 24 98 256 305 156 61 263 287 91 10 217 63 257 397 413 375 270 240 372 398 412 441 261 124 431 77 73 244 282 316 353 200 449 240 195 361 427 364 4 396 341 370 422 30 280 393 218 160 26 211 13 55 146 118 282 270 372 272 334 150 422 46 220 113 57 127 334 97 185 389 186 111 460 204 279 180 214 458 75 153 34 174 489 434 491 138 233 261 69 405 388 265 72 532 223 73 39 529 329 160 158 476 424 167 220 211 423 543 170 76 137 399 527 68 534 512 292 197 125 243 143 64 437 444 518 307 495 465 534 511 438 387 379 208 232 307 56 493 120 390 519 21 65 409 340 65 500 81 435 311 196 432 99 59 480 76 325 292 446 499 458 577 192 23 246 93 254 442 243 419 152 109 521 112 59 405 229 298 576 602 562 548 494 161 190 609 129 309 17 522 76 77 412 337 420 124 84 209 155 567 130 454 441 541 419 595 321 333 225 158 451 434 134 366 223 28 61 284 6 470 243 257 210 69 122 20 95 259 155 346 549 233 18 597 532 128 314 554 237 427 325 370 243 178 664 492 97 572 544 638 472 538 373 627 383 625 307 43 645 243 662 140 118 7 513 183 518 514 304 2 622 27 88 370 424 352 524 408 431 507 422 235 412 144 164 69 600 540 471 620 199 349 189 412 356 219 741 476 287 170 711 641 109 550 376 219 546 471 288 252 75 408 53 114 342 672 321 628 609 155 579 389 76 554 393 632 457 324 732 613 294 742 705 407 628 204 124 593 505 76 616 302 145 643 662 524 465 259 116 125 359 781 718 187 597 202 172 317 218 147 10 150 119 370 314 729 152 791 514 101 516 422 204 744 10 278 811 141 250 626 518 613 97 470 613 146 132 503 764 408 389 443 270 743 10 186 135 292 121 96 582 188 83 25 116 53 62 316 555 284 300 264 100 617 717 365 63 70 466 316 783 687 759 733 859 694 290 429 101 219 210 429 485 407 576 778 282 241 596 786 608 45 727 885 240 34 719 613 191 419 448 803 371 785 262 596 39 614 486 353 599 626 477 237 448 809 117 853 30 176 284 103 701 704 706 305 828 64 263 327 653 414 122 384 894 601 912 321 604 514 284 112 516 467 411 37 229 331 383 700 443 651 50 946 755 779 842 478 85 154 116 222 277 70 532 553 666 352 798 822 716 525 905 789 417 521 887 667 491 278 107 758 637 522 385 342 544 13 682 448 191 959 809 22 588 477 928 231 825 47 572 859 649 147 691 757 159 792 426 18 491 501 240 308 86 253 146 62 615 691 779 877 451 232 352 522 912 648 948 176 46 114 308 441 549 430 364 52 810 549 632 348 432 356 948 396 208 222 294 307 144 426 271 983 629 826 237 231 244 259 449 245 637 135 876 719 696 928 1019 809 917 723 318 130 821 217 671 918 1053 927 16 838 423 731 585 196 742 643 452 980 517 622 315 1057 762 1027 30 490 721 97 329 383 383 63 1022 954 143 843 558 429 514 857 253 202 992 560 527 918 426 912 728 495 971 778 383 447 1035 727 1100 489 274 821 985 849 25 807 565 188 754 975 258 850 988 749 1037 258 207 149 767 1065 993 784 695 227 98 162 340 62 1028 301 417 311 184 263 339 767 848 765 567 797 387 118 403 830 761 914 649 575 448 836 473 742 1072 369 802 468 573 1032 400 820 1169 1176 753 826 936 876 877 751 764 1108 592 673 1076 416 668 1188 206 846 220 146 754 85 586 41 293 921 96 226 755 927 236 655 128 214 1106 744 678 445 1135 1176 1142 159 901 503 403 1220 819 1013 904 747 629 1056 1194 770 745 756 840 136 429 330 310 509 757 1125 846 878 165 784 545 727 1108 378 331 752 309 1130 696 245 992 1114 205 524 235 1001 1221 574 679 79 899 241 35 1237 217 204 1000 381 991 969 1206 1013 39 438 1212 842 1151 700 1190 66 951 64 99 905 223 1010 641 888 730 1056 713 514 566 1033 964 703 60 189 621 673 963 448 177 284 397 852 840 1048 614 110 486 717 654 1288 846 1185 1049 143 1163 334 476 496 854 109 1161 1283 121 113 1216 658 80 759 382 353 1293 179 139 224 1275 1112 630 522 1256 1035 1215 479 569 183 404 197 399 1332 1054 291 912 540 570 752 392 798 365 891 459 1312 456 284 248 1004 942 1071 806 904 1354 509 1325 371 64 827 1 625 960 718 262 582 65 1301 366 527 830 591 703 764 757 189 716 185 633 103 271 644 372 425 142 1342 513 169 1050 882 1343 1202 866 742 1340 687 326 1085 213 9 751 1027 618 1007 1009 653 896 745 44 535 320 144 612 471 7 425 170 809 421 868 1112 735 1356 1249 781 961 1094 1177 1172 816 164 537 21 511 395 924 1225 818 1392 1024 750 182 870 415 883 84 442 238 603 150 1059 214 251 1190 1132 1061 415 1416 496 1243 887 202 738 291 287 470 720 1140 1232 892 769 1297 1326 1285 830 25 1079 550 1200 736 980 890 109 348 944 211 1288 1322 267 1055 144 690 1035 1253 1445 458 1065 538 591 865 178 1225 1337 1514 1180 727 213 1320 725 631 1285 522 1046 971 944 614 1489 964 913 114 554 1104 955 1008 689 1370 969 1149 402 1045 1255 705 1437 1476 665 309 1004 119 1067 692 858 1025 514 483 51 967 448 168 312 1539 299 1528 596 113 449 1327 1207 1278 670 714 1005 1356 652 860 571 420 808 1148 401 584 1037 331 96 355 1403 340 892 54 34 187 1342 294 1102 370 1398 1390 495 1227 1511 1346 43 1486 662 1229 1534 412 688 433 608 893 1192 237 344 1426 1575 949 1172 657 389 1377 1019 611 1356 1465 1348 1453 291 542 1499 602 1139 1579 481 479 940 791 684 747 1297 77 1163 1387 340 523 657 1060 359 137 1465 852 54 1463 1436 967 857 760 1300 424 353 40 1531 1050 982 473 852 163 1365 48 508 628 1480 194 1261 154 867 431 1472 333 1276 1048 137 1053 1196 1129 1413 1339 1125 1267 428 735 1410 451 235 1010 700 1274 474 173 1126 282 1550 25 812 1514 654 527 626 347 930 1715 1125 242 695 767 582 531 739 965 1630 1417 1381 1661 1501 1008 1153 947 195 1116 1733 1746 427 642 289 103 956 1671 311 1737 1645 1746 243 1271 280 878 1475 408 714 729 1450 193 154 1326 1127 217 1525 1234 599 1506 1389 709 111 575 136 822 1782 1227 1069 1679 1119 1047 1390 89 1314 802 212 1506 1173 489 299 693 1426 1724 578 1099 227 1483 119 1676 983 990 804 1711 91 1213 882 1276 560 165 1771 1820 1760 310 49 1298 1543 893 1212 1011 1604 375 515 1313 862 1546 520 110 265 964 708 415 1000 1768 1160 657 1774 1417 1544 241 1035 1307 1843 408 31 1073 264 1596 682 694 872 837 527 1565 1651 978 1541 1508 591 376 821 226 1529 926 1507 1591 422 241 486 382 686 48 1280 1619 867 1684 1716 563 1500 472 1372 1386 501 1867 1417 1756 315 100 1380 1081 436 702 324 311 1631 576 91 677 1635 443 1326 1791 359 188 497 438 1399 1274 1077 1256 1919 1229 185 820 827 1439 406 217 71 42 1427 436 753 1402 454 1290 183 666 856 1029 1313 578 1506 916 1149 1857 5 1088 1524 472 641 804 1902 565 863 207 332 809 667 182 615 666 513 1623 1138 670 581 1162 352 82 1815 1931 1300 243 1285 1020 1330 1845 162 183 690 1419 705 233 1609 88 691 118 891 1527 67 419 1813 1534 26 450 1387 144 878 1414 1146 87 431 283 576 1146 556 435 896 1554 297 1891 1386 357 273 1223 316 384 1002 487 695 1581 1395 1961 1761 1560 216 306 134 918 182 1519 907 430 1984 1453 801 256 354 1056 2024 1369 127 1074 1643 171 1263 1499 2030 979 254 174 545 859 1251 1219 174 956 787 271 1134 399 1519 1139 350 1384 920 1275 1779 1401 54 1339 598 650 271 1789 415 1371 618 1350 1968 561 446 1008 1800 1673 1554 281 806 979 875 477 1775 199 1239 60 1340 1090 1106 998 1887 229 1161 1776 937 1259 520 1344 1275 514 924 1928 432 1674 1413 1894 1471 276 501 1205 790 1510 110 618 853 1281 1519 596 294 1246 1378 719 1381 1387 295 1678 1546 1720 182 1990 1026 1725 933 518 1775 1133 234 760 585 2145 2074 414 1652 862 498 491 2021 556 1709 1046 1224 879 1818 1566 1319 306 27 110 1599 102 1282 1940 245 291 1475 539 419 268 182 828 1142 753 344 1814 495 80 396 833 1889 1274 911 873 841 1945 1185 1309 1193 2103 1049 1275 1277 571 1115 1701 775 2193 1536 1002 549 1660 810 651 2184 1399 1983 1445 1805 909 327 1015 74 637 1554 1253 173 1745 1527 473 230 2080 1910 326 105 2154 1084 664 1129 2028 721 1247 1997 1169 620 1495 584 2224 1137 1328 478 861 1700 1478 1582 551 17 2209 268 1719 1323 1416 1246 556 604 820 1337 260 394 2114 479 1218 128 1924 2032 1645 2089 34 2026 1444 501 1054 722 1466 1252 1231 1513 1222 1202 2194 1369 596 908 779 2170 2276 144 32 282 1741 1954 251 2017 704 1246 785 378 1629 528 910 523 235 1755 302 451 330 45 218 907 2181 297 975 501 537 450 593 632 502 2170 1592 1065 821 95 861 1142 521 1024 1623 2148 2037 1360 1992 2297 1254 387 1170 843 852 1996 1187 2010 831 1370 52 753 338 2175 2159 1024 1974 1296 1411 272 1017 1486 326 355 861 1747 1803 2188 1957 541 849 2352 1364 176 911 1258 1948 684 2354 1048 500 1873 2261 880 317 1223 335 2042 1533 260 1085 1485 1793 2311 1827 1238 1426 161 1593 1891 2367 868 870 2161 1390 2158 900 484 1959 1882 2133 1060 776 284 1983 2312 2086 657 1637 1437 1553 665 623 1805 1202 1324 313 1609 653 1024 44 381 1185 1802 1134 745 187 913 2238 2024 729 1041 465 1264 1415 1110 784 1027 630 2000 1147 1675 2015 1755 1311 1476 1929 366 428 1658 1556 168 2121 931 650 1618 2055 629 518 600 2122 474 724 47 142 857 2064 1272 1092 598 1258 2031 775 1694 1019 1491 1815 954 1531 1938 658 714 2404 768 2237 1240 387 402 1176 214 1561 2161 2347 1948 2461 678 1720 2039 1467 2269 1028 1327 1659 1 2169 2409 737 925 2411 2063 426 1581 208 1089 2153 2455 809 773 2073 2057 20 210 160 2388 1317 731 2423 2290 2517 1331 373 989 2143 677 320 864 585 1034 1602 1390 2481 1564 818 2427 689 1920 140 1385 871 2542 1675 1460 1361 421 634 561 1450 1987 47 1891 282 574 317 958 2403 1894 243 2007 1901 2028 1889 592 2192 998 278 2105 975 736 1258 2214 569 763 2457 562 2353 863 616 846 1330 772 632 2148 441 148 572 491 2324 2602 442 1152 230 2517 391 338 605 952 1293 1941 456 1973 1064 2356 1511 133 1713 1170 631 1922 342 1089 773 396 1560 2367 2305 2405 1539 43 2418 1713 2172 1448 936 2423 438 1380 2156 2146 2329 2290 887 2578 208 1521 2094 322 230 262 960 2524 1789 2334 1948 1152 888 2042 1499 2481 1418 2237 114 975 1245 2021 458 15 302 1860 1546 2258 2080 1294 2110 782 508 821 321 288 1649 619 1695 1741 154 392 476 1935 1201 2296 1656 1226 1572 670 1289 2479 1073 1346 1956 1878 1245 1437 714 274 1912 1690 2292 2025 710 848 2313 677 973 227 791 1454 230 1388 970 280 1097 19 281 2242 926 2401 2057 2074 342 1181 1216 1144 643 2214 1308 1625 1114 1443 2502 2712 1358 2010 1271 2189 2585 2057 812 920 106 826 2083 2558 2191 2301 1986 659 2565 206 2270 805 640 464 2601 571 2301 721 149 191 64 914 1893 711 2227 998 1190 1211 852 1580 64 2076 2001 2213 162 1635 623 1951 126 1750 105 2103 1489 1971 2194 2151 1695 2625 582 2584 304 1285 1876 1566 2124 349 2495 731 1490 1507 255 425 810 849 935 1052 1049 78 989 1454 419 1386 1457 2802 2717 2587 1333 1067 168 1710 2259 1844 1020 348 1624 1041 2583 1027 1599 2258 1762 420 146 584 2016 2362 1017 1528 157 1116 122 180 629 2064 5 864 1162 1571 369 1892 363 2847 1322 2315 1874 1931 2605 260 1549 580 1292 2736 707 356 1354 2691 124 2217 2603 1439 2710 756 940 1953 1462 263 2853 511 2136 890 2298 277 290 1985 1160 2315 223 894 1317 983 1732 992 220 1865 2773 484 1286 2200 2074 1249 2651 2848 2655 366 2408 1842 2793 2688 1921 82 1022 1582 102 630 1746 515 1718 1134 2910 673 1512 339 1440 1902 1817 342 2213 1562 564 799 1693 637 15 523 2668 2256 2182 2929 1284 1033 652 1024 1292 788 903 2330 2131 495 2690 155 2557 612 1118 2170 111 2523 1992 1841 1201 2355 613 839 216 2564 357 1107 2076 1474 603 1810 968 2206 2117 2214 163 1549 1485 1899 1741 350 1571 1118 1718 933 1083 286 980 1955 490 1845 1494 789 1472 464 6 2776 1662 2114 977 2261 470 587 862 937 2586 1473 520 1495 1165 314 2786 318 1709 645 2082 2140 1665 1203 2104 511 2151 541 346 728 2501 1799 2808 1119 163 2659 955 1207 1954 616 2320 1510 2060 2639 1562 1692 873 1307 3029 1341 395 587 1193 298 1703 2933 685 2359 295 2912 1984 597 626 1430 1736 61 268 2312 2701 2172 2234 939 1186 1854 1587 3033 380 857 1093 1627 790 1246 1300 673 1091 514 2429 1109 34 3005 1523 972 1689 781 179 1287 1904 359 941 1170 1829 895 1403 198 184 968 1221 986 902 498 1033 514 2853 2937 1648 2490 868 1230 3099 583 926 1897 1693 2267 1779 1646 974 2878 2911 1122 1111 1167 2936 2165 2362 2462 1047 1025 2219 232 2864 187 2695 818 263 961 652 1126 807 2133 952 2129 266 2525 1184 1882 693 2619 144 1780 85 612 1783 1478 211 22 459 2562 2000 2105 2268 1714 3121 2645 1591 1639 1779 348 2726 895 3125 2422 1170 1091 803 1668 221 3003 2002 1675 1981 2109 753 1556 2822 2096 1644 2340 94 1422 468 579 2061 3070 785 1763 2609 1712 210 1167 3034 2941 2310 162 758 178 351 1027 629 1866 2678 687 737 1928 690 565 1377 795 309 836 2224 840 1978 886 161 1950 2983 416 500 536 1027 2155 2052 1701 2294 2539 2538 993 816 1294 53 2048 2295 2663 3256 1354 3048 1343 2500 1552 323 2180 2385 349 207 2916 2675 1896 1416 2731 108 1334 3262 859 1919 2819 1837 2663 804 122 1936 726 2184 1321 388 2689 2724 2776 2935 210 1898 1609 2147 2306 185 581 496 545 268 117 102 1017 620 2288 2272 477 2137 2591 3244 2449 1559 2085 2547 173 204 1913 3277 167 2871 375 2052 270 1724 762 77 1454 336 2718 2057 557 1470 1212 1575 1986 2302 2769 2768 1692 106 2064 1167 3 922 1048 546 2347 190 702 420 2665 1941 2700 169 2013 3123 2129 405 1566 1088 1471 1557 3118 1074 2660 2035 77 3223 2261 2472 1982 1849 334 3230 2776 536 1620 2060 95 1570 442 2766 1477 2140 1448 174 913 1222 2158 3274 3072 3075 1195 1239 789 447 2250 1492 2029 1257 1674 3374 273 566 1838 80 2060 2547 103 3285 2392 657 2650 2117 2398 1223 2755 2103 235 2765 2636 1813 1907 2626 1920 212 1616 1246 1442 421 2203 3398 2103 1764 3419 1767 2633 935 3024 2673 1449 1305 2326 761 166 3075 2593 1225 2179 830 1858 2087 2024 810 338 123 56 703 2048 2242 856 1 1122 2799 565 1456 2346 1596 332 223 2025 467 2553 3097 1439 377 3032 1220 1057 1276 2933 754 1600 2532 2378 3240 2832 2815 2774 2809 2879 1561 3162 981 367 3193 265 3312 2399 1941 3247 1382 452 991 2935 1878 1079 624 2281 910 2157 665 962 1722 2327 591 2186 3307 1405 144 3116 3306 2005 670 755 3372 2542 2710 116 95 2421 3508 782 2118 1187 2025 1322 2524 3487 479 1380 3238 1021 192 194 3406 811 1468 731 2094 1926 3390 1289 1613 686 1867 3416 2827 1774 1838 1965 3249 1750 2160 636 1539 3289 1899 904 2223 1344 1509 665 2581 1818 3288 1916 3465 2632 584 3042 1299 3361 2761 3316 1984 2009 3577 1345 828 981 2968 2344 1703 3144 861 3379 1117 2141 2424 282 2700 3538 317 143 1068 1545 103 1443 2975 1514 3251 2409 446 2919 695 1912 880 2271 3343 1630 399 2394 3447 1893 2542 1738 651 1470 166 1174 3484 1327 2848 3437 2798 575 3015 1908 42 2498 2963 1764 1845 1892 3422 2387 215 2045 244 1073 2392 249 3311 679 2558 3145 780 1577 3028 664 2745 1038 1857 2195 1657 1217 753 227 2919 1812 3017 1896 2501 258 1613 551 3134 3573 678 508 649 1944 1627 1924 2514 977 3443 953 1675 3331 2529 2617 3672 2232 793 1263 881 1882 410 1299 2561 2245 1223 705 1052 2645 496 357 96 372 2564 1467 2308 2133 960 7 1952 2226 1384 21 832 879 1423 1776 1532 2330 3046 3167 2083 388 209 2504 1319 2230 1890 1779 2129 1706 1906 1689 2781 2154 1071 2717 947 124 1251 3454 2559 2885 1552 3435 3505 518 2029 3269 260 3609 1482 685 2802 2740 214 709 3233 256 887 817 2956 270 707 2662 3253 1312 1164 2969 2128 77 2821 920 2950 292 992 285 1311 1476 917 3296 3096 3070 1183 2765 3479 2393 1065 1748 315 191 2982 1018 263 1731 985 232 585 2159 1350 3587 3484 1029 1761 3406 205 3624 3011 1989 218 2005 2061 1506 954 974 2175 2641 633 1072 40 1313 2012 1769 2802 1478 911 2512 2183 2343 2187 3573 1491 544 1644 2621 668 1085 1063 2876 3413 670 1847 2330 149 3536 835 1216 1234 1086 2226 2180 2004 537 2223 2203 2302 1783 985 390 1565 609 373 3310 1207 235 473 3297 1578 1174 405 1198 295 1142 2346 3555 701 228 3610 331 2332 3082 984 2253 2706 371 1227 2085 3315 1125 3558 1691 503 3808 659 1529 2789 1009 3646 3081 3300 446 1498 2014 1998 1597 2164 2900 1860 2619 2557 3794 1899 3403 1791 3106 2219 640 3351 216 3424 1854 486 2291 2048 2791 831 3565 1913 2652 1249 2241 1862 3453 1930 3342 790 3170 191 1130 1218 557 1976 2594 3596 1573 3776 3161 2249 2129 1479 825 1766 1025 629 3259 3461 3832 2845 1459 589 1166 2309 775 1790 656 1669 746 3434 3762 1688 1745 1716 340 2566 51 503 1188 1337 682 1724 2165