4000 120
1 1 1 4 3 1 2 1 6 1 5 1 1 6 6 10 11 5 19 3 6 18 5 7 7 11 2 5 13 21 25 9 22 3 18 22 12 3 1 13 29 1 25 3 43 43 45 25 49 39 37 1 39 13 21 11 22 1 35 21 26 53 48 50 65 37 51 3 36 1 56 9 44 38 73 21 65 73 57 57 12 5 63 51 33 61 51 45 54 59 43 69 3 72 95 9 7 87 99 1 88 19 43 41 50 77 102 5 22 36 100 33 67 76 90 1 87 47 78 81 119 23 117 13 121 101 80 121 58 31 40 34 109 21 17 117 110 51 54 66 4 67 18 133 39 84 109 85 34 121 6 89 136 1 2 1 156 39 135 77 48 1 141 81 26 95 153 160 90 1 55 99 98 73 65 53 154 13 9 157 139 38 154 73 107 73 173 105 169 120 14 17 55 98 112 183 59 1 108 77 36 171 87 1 77 79 64 152 85 177 2 81 101 195 161 169 211 202 1 209 199 110 130 203 36 149 43 111 194 206 37 223 71 199 157 81 97 119 12 127 115 226 138 69 6 31 225 39 242 183 2 124 120 119 91 236 212 72 215 65 175 83 25 169 160 49 58 44 172 101 93 10 183 107 134 93 38 207 229 217 203 81 124 257 248 43 177 179 113 71 219 187 73 73 13 221 124 251 70 193 242 137 214 237 195 85 298 269 273 301 228 161 144 207 49 41 133 259 71 1 243 189 80 321 248 279 266 212 245 12 215 322 159 158 238 33 162 57 89 137 156 136 170 182 166 83 189 77 13 282 192 188 98 61 254 189 198 254 128 241 96 177 76 335 139 73 97 226 156 201 217 349 365 89 158 149 339 23 177 241 145 323 136 133 321 51 100 235 59 226 213 241 82 200 295 249 152 59 359 385 95 337 390 270 139 363 12 193 251 321 178 329 178 49 270 170 67 221 237 376 54 140 145 107 18 262 419 242 408 276 425 273 235 396 416 213 213 335 73 166 211 136 23 286 206 365 51 21 417 156 1 117 269 255 141 235 350 217 123 249 247 73 376 172 253 61 443 340 19 425 241 192 91 358 157 29 418 93 357 169 388 209 304 381 201 481 227 132 469 135 114 430 378 409 469 342 431 391 305 289 289 285 94 173 386 270 207 242 477 271 376 329 148 86 276 421 162 293 436 273 75 282 342 333 170 299 213 386 364 275 217 173 187 382 251 46 145 332 49 1 231 423 341 433 473 71 483 213 73 9 125 105 351 188 456 410 397 202 307 145 538 77 382 301 386 464 203 143 427 247 446 43 82 225 462 455 282 451 462 526 327 352 539 103 152 395 327 575 538 51 66 49 319 371 120 353 9 144 45 421 11 232 451 103 322 445 131 163 206 379 412 534 171 349 376 427 239 405 219 43 478 293 48 58 1 188 208 581 542 623 353 401 552 191 601 289 575 133 553 286 397 1 69 505 155 77 93 589 499 251 274 519 20 551 645 101 235 424 489 358 37 121 426 55 611 345 387 609 319 199 207 449 406 181 475 43 148 51 71 281 61 221 445 325 14 539 18 413 501 265 148 471 80 390 129 7 657 525 60 572 414 250 168 198 276 58 192 160 240 577 268 548 649 63 596 161 436 505 486 309 505 79 631 516 247 381 603 507 385 411 387 697 204 387 336 129 67 247 475 151 708 167 325 25 180 716 558 683 162 490 60 430 316 498 206 37 488 95 590 276 460 412 476 297 106 40 217 144 74 756 200 25 515 665 181 50 547 554 620 82 688 358 229 507 219 131 660 397 659 748 163 100 716 510 565 649 172 400 585 571 736 539 639 49 505 799 590 150 556 739 115 547 556 573 593 273 269 687 275 401 598 497 104 820 142 219 788 397 569 409 392 823 353 565 829 497 56 277 343 265 363 243 530 140 66 463 258 351 10 777 698 397 767 3 726 189 228 489 16 737 33 381 161 505 665 441 86 777 317 492 783 90 205 135 671 476 811 491 70 466 778 133 523 94 28 387 279 463 173 445 591 429 541 121 873 641 316 821 441 476 449 203 56 347 362 857 893 845 14 114 751 581 807 359 327 541 849 433 540 1 290 423 588 457 150 192 646 786 93 859 661 297 400 145 507 7 279 743 694 331 84 655 192 449 379 892 364 367 726 640 723 461 517 307 367 559 895 12 692 181 649 744 714 638 628 143 701 21 460 881 960 589 374 359 700 655 947 131 722 657 536 773 434 227 621 109 821 689 426 265 37 25 114 797 256 57 932 349 358 841 317 706 206 284 925 591 395 726 382 607 643 210 34 487 267 937 88 307 902 592 627 771 166 463 671 586 471 866 820 691 685 173 949 463 459 869 829 291 823 189 138 659 1002 379 700 689 118 233 488 661 931 517 1015 634 975 743 850 841 388 460 882 321 631 768 570 693 434 509 563 70 266 773 299 889 51 17 383 677 384 921 664 878 707 345 1072 580 1059 113 82 1079 349 857 436 937 1050 7 1058 541 440 781 100 946 412 877 443 74 352 555 547 40 1024 416 413 1015 484 265 839 809 728 966 11 379 670 399 52 981 1 535 715 1093 796 897 57 1111 1044 1034 1111 817 917 866 419 191 853 298 861 745 939 747 688 1140 865 641 378 1123 369 271 887 333 367 854 1064 185 1059 712 808 511 361 907 936 110 822 499 474 283 318 466 655 279 953 69 1113 877 574 543 973 1163 298 353 1108 205 22 353 527 565 563 609 1072 280 870 541 176 1057 965 197 1073 963 597 889 1031 393 332 78 56 603 737 830 804 583 1104 1077 1057 537 1032 1209 591 715 844 1070 798 570 693 1041 707 925 381 19 328 641 819 1187 173 915 991 1029 454 763 970 812 452 585 796 474 875 1247 580 1065 706 1213 1164 69 326 825 1139 1230 618 1222 911 729 907 385 732 913 1267 1133 33 1098 124 1213 201 51 1110 803 276 983 270 72 67 1075 1279 333 169 43 862 614 919 727 153 529 933 1025 351 596 300 1283 1132 501 458 417 1105 765 1230 125 857 377 156 523 96 823 1087 321 37 1003 256 309 225 409 99 1137 34 1143 1306 73 467 599 921 753 1239 1027 245 489 720 1104 339 361 671 839 991 317 603 535 386 955 19 40 671 419 1034 329 646 787 269 809 157 157 1174 939 1028 1333 780 154 1258 735 640 975 1002 251 1338 417 625 201 333 873 724 728 326 635 1356 277 213 374 826 539 918 233 1106 833 503 531 133 1265 692 1149 1219 193 1125 1078 453 820 1241 1297 569 17 607 203 708 1121 1084 713 343 1087 467 519 980 713 1204 1329 752 1071 1290 1389 595 200 847 875 1154 753 865 551 373 631 1337 1131 1375 1141 1191 1185 1087 1209 1072 432 164 1051 1214 957 557 1137 1411 844 1299 49 555 421 1214 1225 344 332 111 796 410 961 998 513 76 1231 251 37 596 204 1249 101 1175 262 1151 351 284 1155 991 683 313 1345 1281 685 364 1305 565 1441 1020 1267 488 1137 220 1019 1119 9 1260 1483 404 1189 664 227 732 883 199 1055 1396 725 241 529 596 93 205 85 527 669 214 1245 403 69 692 244 401 27 1495 335 1454 433 584 509 714 617 94 751 843 946 178 1126 1107 1129 666 463 1430 1049 1306 1027 569 637 707 811 1173 1433 1203 1216 1231 1473 1054 689 1270 797 961 271 150 1297 1103 116 226 1350 192 799 961 1000 1117 897 412 397 1216 866 1444 853 1465 301 117 386 649 767 779 1021 925 535 919 980 249 991 1400 1065 762 469 1037 553 913 1471 1254 793 305 1120 1409 1585 1303 558 672 171 1431 1431 1372 1505 430 1232 1252 845 54 1125 41 595 1357 393 1451 391 310 503 771 1354 262 1024 643 1165 1354 515 1276 563 1282 609 498 1045 1045 77 1200 547 1393 1455 1494 697 382 377 88 1041 681 1 800 693 255 757 646 1253 691 259 452 1369 1562 637 1474 905 1478 67 1316 965 1513 757 1226 813 1318 371 1218 397 70 1099 1649 153 1514 997 1391 1248 1645 162 402 769 606 478 576 505 1707 796 735 1669 172 1299 284 628 901 849 220 782 1182 151 582 329 961 361 1421 275 501 919 388 1123 72 1169 127 1709 1539 536 1219 55 220 307 418 546 1071 691 577 1491 678 1604 155 64 1309 1498 767 1373 471 805 1729 336 1125 1215 1404 1093 1416 819 1537 358 497 175 1768 341 229 1183 631 477 1247 1427 1152 52 1433 1131 961 425 454 763 1410 264 1075 501 263 1449 87 613 1638 312 799 1567 1338 1675 1696 624 1525 548 375 391 18 1668 1280 951 1606 1375 1482 199 905 511 557 1711 1101 1541 1011 1383 1286 678 1204 1279 320 981 1007 1555 1256 1261 1171 99 5 687 105 423 1250 836 1543 743 243 1360 865 1557 1037 1577 1594 57 1660 381 358 1652 1471 21 259 771 524 1806 1655 1521 167 1087 1612 1021 1291 538 802 451 1402 325 1435 125 1509 1744 1296 1391 1283 733 1783 1595 1215 1753 505 139 1148 1253 668 455 1168 734 688 1035 1219 1465 1807 1153 778 541 1614 1183 836 267 1261 907 1440 412 694 1361 1870 432 566 19 421 165 1470 522 850 376 159 1695 425 1814 340 55 1342 955 793 834 892 1513 1552 1191 1911 1721 699 963 883 1061 78 1516 693 931 462 1250 702 1205 1870 1603 455 25 340 1207 1684 49 1523 1053 1578 1520 1683 9 1925 134 1393 1165 176 1952 1622 1554 1567 1128 616 1253 409 313 652 757 929 898 938 527 1411 1535 549 1371 394 1687 820 1031 824 1873 1948 339 1735 1593 1223 1863 1610 1026 1385 527 325 1081 1857 1888 61 1699 1387 1873 323 1485 529 985 1298 195 1633 1170 208 944 907 474 1156 1027 1279 1663 84 886 569 748 682 1709 1064 706 1703 1672 1239 937 865 168 2018 821 717 910 1187 529 1991 557 346 1223 910 403 50 1893 1451 1469 1234 15 2028 523 339 151 123 928 541 1495 16 1034 1417 1201 208 660 744 1001 1631 1509 339 901 494 1301 1195 1856 1040 193 153 458 2044 205 525 1997 1642 1070 977 1057 544 588 1101 2056 1811 451 477 935 1303 2043 236 1006 1019 1999 857 556 248 899 1205 1597 1288 1253 880 1698 1292 1411 1526 1927 1478 1645 2116 1205 1819 305 2091 1758 1175 92 1999 713 1012 421 1900 2133 668 723 1983 577 432 337 1396 620 1541 1233 809 1576 229 89 1221 865 173 729 1105 1055 1135 467 420 2055 1359 972 1710 1129 1386 2049 301 1252 183 1865 290 1550 1435 1609 1438 1583 1918 1052 1606 28 1274 1651 277 798 1770 473 1919 1046 414 2033 1907 245 1911 945 1938 720 324 625 603 1213 646 1113 1216 247 847 509 1626 948 538 447 586 316 1681 1867 1044 801 1551 183 484 1699 1207 360 396 589 1643 1141 2156 2051 1213 1093 1044 2165 730 1992 614 1181 358 533 351 1475 331 1345 790 1735 682 1393 1220 1163 381 1319 1463 1825 2201 922 411 1711 2083 89 596 231 1814 1059 34 891 1240 1505 1617 47 1614 1861 1428 1702 1115 1361 234 2133 432 292 2160 929 178 2097 597 1509 2200 540 204 929 183 776 1408 454 1987 1907 39 977 782 465 421 174 1278 1186 717 1115 811 745 2300 2125 623 175 1844 197 1817 1422 1455 1689 1978 1908 986 1647 912 166 1894 1117 1698 777 2010 2317 534 1585 558 1213 1506 1726 2056 364 2074 1740 1373 2015 474 41 144 1376 605 237 2242 1352 388 1908 1616 39 1094 1955 934 339 1492 141 340 1823 72 849 1261 1899 390 1794 531 244 989 1315 430 2180 2328 2329 1562 583 1137 1408 39 1221 1008 2373 1846 935 1167 1475 1325 1887 652 984 279 434 963 1149 2263 241 1526 1305 2297 2054 503 1419 2275 2125 509 159 2338 481 2232 2404 971 15 1519 644 1629 1319 1778 717 713 1105 2063 1721 764 1512 156 701 1520 73 2380 2041 1354 1094 1933 1561 1919 1611 1189 581 744 2001 592 31 1213 886 1525 1 202 11 2338 971 563 1061 2342 907 1730 1483 439 985 1437 1883 1056 417 2126 1820 313 534 2462 183 148 922 1956 768 2318 1777 1554 1183 447 2016 115 459 1246 2101 2479 1635 711 1191 2413 881 268 2331 1565 2296 1462 1141 1073 1719 1177 139 575 601 966 816 859 1267 2033 1563 2124 1534 1378 1114 2146 1441 261 361 1228 636 1700 251 2163 233 1470 1701 1435 2110 867 2369 376 606 129 545 318 1828 279 270 917 703 763 488 1081 974 830 591 1545 1564 20 2469 216 1945 2369 913 1616 1677 2376 433 1876 726 334 1985 9 511 2030 1649 1627 1765 677 807 2560 285 1717 605 631 2150 2001 1744 90 1413 1619 511 642 1647 2437 799 334 1407 1698 977 132 15 513 609 1013 550 503 1685 2299 1717 1722 2375 1738 875 275 2331 2425 303 1223 620 928 1576 777 1094 827 1035 1028 1465 254 385 1292 1893 1879 2115 748 1633 1323 1302 2586 1949 2477 187 1137 127 2342 2407 2425 873 1528 713 2626 529 1330 1638 1424 1029 1891 2397 1005 230 884 2447 2157 2129 1107 804 728 1912 538 1476 278 263 2367 786 1236 409 2186 1300 119 1955 1228 56 2631 1721 2476 1667 785 1985 258 1474 2227 2097 2339 205 337 1939 1994 1961 1553 959 1706 2082 1483 2295 1796 133 1658 921 721 2629 1720 112 1597 1073 2109 2699 667 2083 1912 1213 29 274 389 2040 1458 2364 1966 1913 411 121 924 1167 1390 2622 160 1273 1766 783 714 2124 507 1393 1036 25 528 881 351 872 2259 1877 2330 1486 795 991 907 441 676 594 649 359 2398 2709 2038 1896 1608 581 2003 690 2684 505 1702 831 2212 2664 2004 2170 396 1900 1756 1167 1769 1499 791 1111 2654 40 589 1257 429 2542 476 1441 805 2298 1761 893 296 484 1376 1889 1762 1501 2227 2489 850 977 2428 1761 1452 261 406 2167 1331 1975 839 1685 1395 661 1667 635 592 2207 2701 790 195 2803 21 1197 173 881 2538 67 15 2777 1009 2255 1562 2575 735 2045 669 1471 819 445 2468 1448 2215 2433 1448 1113 515 2273 55 1147 355 1609 1818 2345 2214 1705 1051 2776 998 1543 1297 163 2285 400 1398 2211 262 2229 1839 2387 2793 783 124 85 1372 718 1935 2477 2128 34 2670 2347 602 877 2752 2715 2479 2554 2468 154 2311 1108 1797 2689 1374 1272 1000 1616 1647 2845 369 2432 1002 1820 1641 841 2056 890 2864 1765 1104 273 719 1567 1730 831 763 2047 392 417 2368 1800 1408 2031 1866 869 1554 283 1351 1315 1202 1471 1458 1633 2311 57 843 1213 619 1539 357 1077 1039 2081 2079 1523 1286 2821 2940 823 1609 1183 1297 64 1224 2355 2341 1581 907 2566 2298 1916 2715 945 1955 1339 230 2046 89 2595 2026 397 693 1330 118 2241 79 826 1621 281 2908 369 883 2759 585 568 202 255 2048 235 765 2177 2486 2159 756 1401 824 612 1219 2199 375 895 2196 498 2834 2116 1627 446 1785 1601 2651 204 2275 2913 2285 1745 1770 2007 2301 2317 1370 1966 517 321 1436 1175 187 2641 2047 1625 1617 2521 2740 1151 1436 2393 2879 2219 2675 176 2477 2139 1171 1993 2076 411 697 2471 1014 1000 2592 2914 2884 1703 2181 857 1100 789 1046 483 2628 459 732 1215 1188 412 2325 2767 2745 1126 2017 771 2483 2989 1678 2539 823 806 736 2200 1154 583 1897 712 2825 124 1076 81 1582 845 1230 1213 2681 1391 1548 1293 1974 1091 2072 2053 736 2285 2104 2075 2535 3010 1839 397 2799 599 801 1435 1105 2242 1788 1758 916 221 2114 1017 2508 241 920 2116 2153 3009 47 1363 1535 2696 151 1897 1207 907 2216 211 1639 2618 3026 2163 2417 611 100 187 1553 1194 1760 1917 3132 309 807 1937 548 902 1795 881 2144 1177 982 2120 2941 989 1391 1501 1099 887 1162 1765 1044 301 368 1325 2697 1839 1465 436 906 2961 575 1427 2546 995 3165 2072 2815 905 2512 949 431 1242 845 1705 846 3100 2742 811 61 879 86 1372 2379 1652 1693 1893 288 1983 2765 2425 2377 1222 2535 2410 710 2241 1561 1843 1356 1090 887 247 1631 735 2700 262 1641 2411 1139 2379 597 2533 3034 2479 2480 3041 2717 2520 566 2406 1828 2466 2834 672 2353 1825 2844 619 2079 417 1625 621 2606 1327 719 1180 1121 883 2555 2091 2300 2929 2628 1411 391 936 1039 33 328 433 1843 1184 235 436 1571 1707 1540 2433 1845 1696 546 1707 1194 2115 2167 1189 418 1991 544 1761 233 827 2092 699 1534 1332 2761 442 1468 1349 1240 1145 384 2143 525 1669 3022 2467 1758 2797 2008 1503 2770 23 2632 667 275 605 1945 2234 1451 2133 2069 1015 2815 2619 3269 2121 1347 2676 3071 1135 2264 1979 1791 26 2477 2929 2748 2717 1934 1033 1906 2645 1874 3162 3071 2156 631 1696 1755 2321 1011 2705 698 2922 1752 2879 205 3085 1035 2468 1645 2431 2529 329 1765 2162 1390 2401 2572 2270 1525 3225 3216 834 1470 2710 2287 1172 3122 1725 1003 1211 2948 3015 58 1805 1424 3053 3368 2516 405 1885 40 2177 2434 2145 1286 1831 1817 3029 2445 3386 1376 785 525 2545 2900 1273 904 627 1553 2690 1561 277 2106 1612 1799 1489 1285 341 1 871 1946 2829 1327 605 3418 493 186 2449 3201 1327 2453 1493 2319 3201 1081 2411 968 3138 2470 1843 670 379 2852 1643 164 1217 1117 1065 2102 181 1326 2168 730 1035 2862 2501 2369 209 2949 1979 611 806 1780 2858 433 385 2237 3183 3273 2701 3385 505 525 145 2530 1111 2011 598 2679 852 1264 282 3060 1994 2066 1249 2503 1323 3179 711 594 850 3004 225 2934 1696 1284 2396 3443 392 1939 3361 2175 1507 1711 1926 2902 1537 1520 2831 381 89 3326 2157 1644 761 614 1665 1717 81 2261 29 1193 2847 792 1079 1006 1261 972 999 2335 1291 22 2591 687 3191 2069 2565 1083 883 492 2033 2820 3335 1085 1040 866 3541 1148 1355 710 790 463 1761 757 2351 1997 445 662 105 92 2753 184 2555 1426 2281 214 3050 2196 3318 3534 991 2649 373 11 656 1587 3145 3429 1654 650 1286 426 2705 2986 398 275 1627 1451 2740 2521 2717 3229 767 3511 2233 3433 3179 1705 583 1653 2305 1998 2739 2158 1037 3167 1491 578 157 3581 2935 3445 33 1360 2895 782 640 3115 2763 2873 3355 2566 618 524 1963 2629 745 340 2044 2994 679 1091 2102 2571 441 3611 2907 3436 633 716 2891 269 2117 3279 3369 1898 419 432 2123 1075 804 950 2585 1654 3408 2602 2946 771 3501 1845 1917 506 821 652 1207 2746 81 561 2759 217 43 2703 1569 1303 2173 71 335 520 1361 2276 3655 282 907 1471 1461 3617 1651 2280 1066 1881 2485 390 857 2954 495 2523 1799 1912 2205 740 337 2909 1988 845 2921 3243 2751 1615 1715 1615 1159 293 1851 2180 2196 2734 853 203 1720 2246 2149 3516 1483 945 673 2889 3323 50 235 394 3326 2258 871 3118 3681 1713 2770 1241 1117 1771 175 505 1639 677 2473 3388 2511 1173 58 211 466 2755 2113 1841 597 1076 29 2039 491 2093 745 2700 1679 624 843 1969 3359 3738 297 1921 2518 568 1621 1843 188 1276 3032 461 2267 1596 241 681 2807 2607 3116 2659 1723 2581 265 1578 271 1626 3085 1495 3045 84 1005 79 2843 496 928 2988 2527 920 691 1939 872 2705 3569 1102 3343 185 815 2637 2425 2541 3229 2531 848 164 2661 259 2979 232 2431 2750 1316 1820 3109 1579 1841 2891 1821 1937 3344 127 3625 2188 1096 3655 1681 3481 825 285 961 443 3051 2882 2763 547 3535 1919 1633 1958 2381 3554 1610 1912 3346 3211 2737 1094 2288 1936 3445 1189 2037 1884 2379 576 1148 2233 1627 1982 3301 1748 2223 2208 2644 1396 201 3145 3000 1133 2437 2277 3595 200 3801 3484 3696 612 1450 1731 3036 2866 2267 1042 3125 1290 1401 1270 2811 3827 2629 3655 2373 1108 2471 1 1786 1873 3835 683 1116 1506 877 3674 3802 2286 1012 1061 121 2246 1721 2038 2729 1009 2581 1102 102 1140 2598 1809 730 2576 2137 592 1179 2606 2229 2718 2713 3293 509 1384 2452 1967 929 1511 1359 2424 1088 1298 2026 3319 1313 1998 1447 1639 1034 2939 1245 995 3495 749 3177 1984 681 338 2931 1257 1198 3557 352 2203 2140 96 2526 1447 85 3199 307 1002 3265 76 661 2987 3321 1193 99 2392 3915 830 2609 688 680 2973 521 2815 1160 1791 1489 1772
1 2 886 26 2029 3488 156 335 974 1700 3588 1879 3087 2213 439 2460 2561 2677 3122 3372 3673 954 1053 636 3482 1463 2254 1916 3933 464 567 512 1974 3766 2530 823 1040 3543 1319 2943 1770 2188 3099 1860 3620 370 1871 2101 1316 2474 2796 212 3815 689 3155 1047 1567 1972 2907 3633 1114 2513 513 2494 2164 3373 3 6 136 412 612 1247 1787 2540 2910 2250 1909 3059 414 1994 2686 3479 2192 2284 3558 2296 2495 2883 343 840 384 1080 3294 1396 1516 1943 2146 2514 3876 3842 301 796 1132 1306 1332 3287 1554 2920 1252 1628 2171 1819 2259 1195 2082 2691 1496 2765 495 2761
