3499 9
0 1 2 1 1 2 4 7 3 8 2 1 3 8 14 7 11 7 10 7 13 17 16 15 24 12 24 14 7 28 27 27 15 12 2 23 13 30 17 11 27 14 33 34 41 32 17 4 47 49 26 42 18 9 54 2 26 51 46 28 34 7 55 49 60 54 41 52 54 28 13 68 64 25 32 7 64 53 12 40 39 43 19 37 44 52 70 14 47 3 16 20 39 50 69 49 51 56 76 35 32 74 4 81 54 82 16 58 32 59 60 78 107 85 28 57 49 76 23 14 54 114 102 119 47 4 1 43 43 3 104 97 98 83 121 112 88 46 47 88 75 10 58 117 110 112 6 29 112 124 26 36 142 20 118 94 57 118 33 31 11 136 114 147 149 60 17 142 19 101 150 7 97 23 71 135 118 46 51 90 25 88 93 171 174 122 22 93 111 160 76 154 78 168 43 113 108 175 124 24 34 25 173 198 182 83 200 82 57 86 53 136 47 70 182 173 3 81 71 41 101 175 146 53 49 16 25 161 213 68 128 1 184 20 139 16 123 88 25 47 70 111 121 187 203 64 181 48 221 198 47 172 168 170 47 117 201 89 148 54 187 87 246 34 155 128 200 41 162 141 214 230 265 214 155 75 200 202 173 258 231 270 29 29 122 106 11 274 172 146 91 272 244 191 182 139 76 112 227 102 118 177 123 63 31 112 280 228 234 25 47 289 207 259 5 278 261 68 101 317 247 225 37 73 246 101 44 26 160 280 152 44 265 89 152 197 203 194 261 154 2 52 188 268 161 9 243 235 329 346 237 181 13 318 11 174 7 289 174 34 252 345 347 124 173 126 100 363 282 362 335 77 203 55 352 94 312 48 174 312 186 297 209 150 301 339 224 373 134 94 347 55 99 170 247 128 235 93 94 269 274 136 274 232 302 328 332 164 32 406 135 332 179 88 130 269 382 253 50 366 149 86 347 416 417 175 90 334 54 130 34 143 49 104 195 396 17 22 343 268 7 285 253 262 84 272 376 409 121 400 126 109 243 37 43 180 246 204 252 216 341 266 366 133 157 451 247 391 141 249 4 30 459 99 129 347 448 246 219 249 29 412 225 188 332 471 231 428 302 212 46 292 194 233 155 406 364 269 1 433 287 255 271 13 53 492 329 169 369 158 24 251 255 401 117 313 494 107 404 270 480 329 53 218 145 247 72 237 183 441 204 346 51 322 155 26 433 120 458 108 483 337 298 220 301 174 36 151 283 502 508 496 215 318 544 300 54 411 440 138 8 410 406 43 139 505 493 447 151 39 196 432 517 253 559 483 305 554 248 451 460 230 507 292 140 377 108 506 588 552 92 358 244 234 6 379 89 174 403 532 224 209 253 461 224 235 289 112 32 99 378 550 208 509 400 437 492 261 348 175 175 386 577 62 76 418 452 294 459 85 568 560 414 4 602 498 337 364 115 20 176 208 201 566 60 487 428 535 138 325 589 464 55 644 411 118 2 71 196 639 348 19 537 437 331 590 313 431 368 519 598 7 114 304 621 272 402 110 607 1 515 307 67 41 273 52 87 369 36 20 432 289 174 395 153 518 469 260 582 185 498 661 177 32 201 526 72 495 241 459 463 567 561 449 592 486 486 569 511 470 229 226 714 408 500 390 263 468 293 620 38 313 241 104 228 371 639 646 268 16 34 406 414 262 481 502 205 696 57 510 53 578 365 333 576 48 697 747 429 48 713 498 381 703 132 21 491 6 613 761 515 149 341 145 609 438 612 131 565 174 36 665 427 216 278 237 114 177 79 409 779 656 216 73 614 42 279 511 232 501 222 511 159 660 783 567 798 233 20 644 657 4 103 805 628 550 741 620 230 353 545 310 398 524 445 618 221 762 259 716 516 361 29 38 583 422 59 314 548 779 696 474 72 805 434 163 452 229 252 625 542 599 845 340 89 671 90 394 807 571 574 549 530 700 743 752 815 591 810 384 498 68 464 85 640 329 614 105 405 78 53 62 525 236 274 883 102 410 767 475 713 611 545 682 248 432 736 328 678 14 720 523 876 550 132 149 618 600 363 474 570 452 39 192 798 639 371 10 916 95 485 63 126 654 419 612 257 734 697 3 362 21 862 151 298 306 223 419 431 377 926 227 737 22 168 246 291 943 11 555 920 804 72 799 737 161 288 233 386 855 35 602 959 566 388 892 600 718 695 148 902 219 582 25 218 783 385 945 583 203 243 430 376 82 133 391 653 235 822 610 742 452 404 463 81 971 766 692 83 669 592 742 717 409 447 991 436 772 376 761 137 35 959 686 48 249 500 780 190 211 612 115 741 799 594 266 728 741 400 176 258 107 1001 66 190 1032 194 527 551 384 22 164 853 590 630 950 990 796 541 954 4 892 69 284 26 4 112 208 539 729 229 1012 707 930 661 72 439 996 969 407 195 568 732 71 1011 1001 1032 647 261 468 85 1063 318 226 460 654 125 454 1045 407 252 705 93 417 346 67 220 222 523 790 1095 308 454 303 99 12 490 916 431 265 7 773 620 348 863 498 156 866 1089 117 824 1030 545 868 154 356 328 5 666 648 425 823 716 585 715 325 157 280 71 663 426 1012 524 330 1083 246 706 1133 403 191 326 890 338 204 578 462 1064 1126 241 354 827 451 35 91 697 125 1108 242 549 467 545 120 376 217 569 134 130 1092 468 638 745 443 714 735 621 546 1053 1142 644 840 29 1168 845 1167 112 718 598 718 1031 899 107 12 784 969 169 897 537 545 36 695 485 653 379 1061 245 522 765 140 957 183 458 736 170 672 699 279 286 1167 319 767 1063 379 199 254 895 1028 1117 1212 200 169 556 786 611 932 161 498 36 747 1064 385 227 627 358 521 881 384 809 1181 683 280 903 1142 605 884 608 239 905 799 403 481 1242 231 53 16 983 1099 738 646 520 584 1101 227 560 824 223 559 1133 977 1122 1241 707 1107 608 1140 911 651 1156 237 515 1058 862 318 174 331 948 1121 1273 823 110 1030 1164 1171 1151 762 250 425 996 876 538 1228 476 607 1037 622 1184 969 601 410 939 808 91 1231 88 1328 1043 831 670 353 346 1285 121 612 237 1011 748 35 856 107 291 1205 539 864 897 614 791 439 1087 840 1216 409 288 1144 441 538 244 474 940 183 620 43 635 938 815 516 834 268 931 787 945 1257 341 1279 828 429 41 862 327 196 946 1190 9 1318 462 860 313 3 829 1170 1297 592 326 792 1287 1294 260 531 769 28 858 225 869 1032 1168 464 667 804 1306 455 1343 407 390 712 1128 270 1226 368 440 1215 1420 1115 1133 256 680 1241 442 1251 737 459 1068 913 1316 1222 709 1438 119 323 1073 1224 552 451 472 1116 520 906 835 947 59 345 1152 398 1378 1263 835 837 1144 896 3 796 1379 881 1209 1070 413 739 1254 912 163 137 892 1363 76 1440 974 1349 1440 1145 1486 504 370 757 72 781 493 1382 189 1306 564 764 991 552 706 1332 814 1065 1326 1182 1293 926 1443 467 668 375 377 919 715 281 37 413 851 282 825 431 1316 323 33 822 1389 251 120 1361 946 71 900 877 180 1212 1192 232 1370 643 1138 236 1202 713 1449 1200 1278 1029 176 265 187 711 925 1224 87 368 1163 294 1416 1078 82 182 482 450 1086 1402 67 895 1028 714 212 1216 342 596 1156 483 487 471 1356 1395 1549 1116 222 759 407 216 485 927 1546 294 207 493 1005 1014 1160 1098 1296 698 1183 1246 1009 220 908 389 439 158 1368 379 915 1539 533 1442 1122 776 1593 661 723 1110 871 1538 433 995 1113 774 66 314 54 1579 352 1418 322 792 1308 1258 1393 781 238 206 597 643 659 1623 1252 783 690 1119 1586 1205 328 330 1517 1178 824 588 1561 254 948 968 900 1410 1618 847 196 1009 1574 509 737 185 292 139 1077 1400 1587 386 1257 775 1378 795 1427 522 1418 964 173 1427 292 377 1051 741 17 1264 1393 633 1505 542 278 73 725 68 898 453 1431 832 531 516 1291 852 1065 609 71 225 1512 1599 945 40 496 69 795 1256 738 823 1014 100 1112 511 1645 1453 1370 583 765 705 1209 687 1105 1443 1164 1465 1321 709 717 339 1696 857 891 1117 687 274 1438 916 1536 413 964 1181 541 470 472 1611 1274 1118 751 975 407 1193 511 1341 987 1413 1754 57 387 972 561 1720 1743 1756 1251 462 1217 1351 631 545 847 1456 152 834 902 1404 1400 864 949 502 169 1592 466 1479 474 1225 1122 817 1794 1417 471 297 581 202 1003 704 1451 327 1431 1284 308 55 462 449 585 550 1094 707 1044 1661 407 1257 1689 493 659 836 1033 80 896 1235 1609 562 1380 780 1360 693 1199 76 1481 621 1725 716 395 1447 1727 1706 222 1088 202 1196 694 837 1788 119 783 855 730 1618 77 780 969 792 857 1476 1320 702 1568 1140 1471 497 1170 712 723 1156 874 1313 727 984 713 1221 727 150 1076 1585 1151 127 1431 1087 1832 1698 542 1143 618 102 1385 218 1870 282 1301 873 549 1247 905 354 1822 909 553 671 1606 486 675 942 394 1881 1469 1757 1609 384 1704 1908 927 1170 175 898 326 1836 1271 423 585 1220 89 468 1257 1598 1278 1204 1435 507 1111 1889 857 439 614 152 639 1630 666 167 976 1428 768 1112 1582 1001 240 346 1053 1687 954 136 298 1564 1742 50 1248 1766 194 1533 1065 773 837 79 575 767 265 1360 1759 1356 588 1938 150 297 1323 1518 1217 469 1113 711 565 890 109 1205 351 1604 1381 1414 1381 950 412 155 959 216 849 409 695 470 1339 157 1169 732 418 1468 1410 479 1694 469 313 1371 1655 1059 1061 1932 216 1257 85 945 1454 1295 1866 182 151 709 60 67 1970 557 1273 440 963 515 628 212 224 263 211 1096 1138 1692 346 1168 1465 894 2047 1549 253 220 1183 484 61 1642 1815 38 1057 585 900 1952 1017 1182 1374 947 1380 1182 1625 892 1663 1759 661 530 1283 1798 127 577 1137 1705 141 11 970 1228 1576 152 1659 1843 598 1662 317 1801 527 1731 1914 99 23 165 633 248 1358 105 1605 222 1195 116 1219 319 698 239 22 1045 1979 325 1238 1949 620 60 252 1174 1055 625 363 2043 1822 1923 2054 423 865 1381 1185 875 1080 222 1210 914 1992 470 2128 1256 1068 1900 612 1234 1181 1904 253 646 431 372 1971 195 243 2044 2050 1901 1241 1509 309 348 2134 1151 314 1079 763 2030 1925 2169 304 2082 1884 920 1967 1150 967 1185 972 1793 143 1843 1769 1437 478 1612 2187 1280 1416 519 431 875 32 1183 1035 754 787 70 1981 1766 460 1604 1903 1990 1074 898 1047 398 2191 601 86 1717 1648 440 1197 1851 169 1337 468 755 1115 1969 471 379 739 86 627 608 1339 1563 168 172 917 1745 81 1918 220 1824 1880 948 2157 221 1740 1587 930 1665 1487 1388 1037 2092 2020 459 446 1591 1542 1135 1712 1024 2113 1339 584 2211 133 984 987 2116 1337 1924 767 2153 1933 1031 907 1884 199 1996 298 1400 2014 706 1493 2275 520 40 1113 714 1180 2067 1210 1076 1607 109 115 1468 1462 506 139 602 113 361 1314 103 362 1110 1892 1469 1190 1459 39 20 916 1296 1252 555 436 1536 342 775 1285 50 1255 1361 1260 1427 295 2183 789 1832 2232 1035 987 1661 1794 526 6 694 26 404 157 1812 1360 865 491 1896 68 1704 1238 1884 36 86 459 890 2263 1443 112 692 1640 30 740 967 1141 934 718 457 1935 853 1276 999 983 471 377 498 507 2077 1189 266 1825 2154 2161 959 1976 331 894 211 1438 2070 1428 528 934 1710 431 2074 231 1772 136 48 1558 1332 848 1258 2098 216 2063 2198 1417 126 130 1363 995 1237 945 367 375 494 686 87 1206 1192 514 65 1613 551 1683 1964 357 1901 756 1522 2093 726 1794 807 1141 564 734 556 888 544 287 600 836 1401 1427 432 481 407 1879 1074 938 1153 1747 2298 1097 1403 1238 2237 1566 1911 682 1743 163 535 104 494 985 1157 2230 642 2260 432 1024 242 2056 1756 1707 1163 733 1227 2064 2022 1716 1731 1732 2359 1128 818 1252 2139 305 2417 1934 616 2102 1011 81 1913 518 1967 2231 796 2132 227 919 1653 2422 207 1821 1519 893 796 2030 479 2491 568 1767 1467 447 2055 1562 145 498 2141 1579 2364 2161 1441 1697 1853 2240 1184 358 1543 2268 2200 1130 942 2282 2450 183 259 1003 2282 456 1340 432 2115 282 848 141 237 1181 1305 2220 1383 141 2332 1874 2486 1724 1292 309 699 1790 1524 2542 688 1351 2325 96 2074 957 2546 69 555 1773 1599 2257 2050 2269 1500 1364 1705 1941 2049 643 313 2558 763 240 2287 1100 251 1957 2023 2513 1784 352 2112 1943 493 694 718 2337 418 1119 2386 1087 2595 1007 1284 1199 2605 483 1765 192 1306 1796 25 2406 959 828 1683 26 1552 2075 1956 2284 1523 2550 2388 2491 1061 2379 1638 740 1228 1331 626 278 2532 2075 1737 845 1907 973 1286 854 3 2518 2547 2231 446 1744 303 1357 240 1438 1188 206 1965 2340 899 1884 431 2178 1501 1112 358 99 1266 1099 2233 2306 700 379 993 1900 605 88 2430 543 1054 2237 991 220 456 2593 2177 746 2042 1378 1925 1637 1107 1242 1683 61 913 2621 903 1903 906 260 795 1075 397 779 2390 1318 3 262 1911 2349 1074 1424 148 650 944 2002 2317 323 1416 1392 700 2143 1738 1049 2644 276 2165 2127 1595 1886 1768 500 675 1400 1416 351 2254 1466 27 1497 624 2143 2041 1975 2601 1899 2450 1426 680 399 1976 402 1490 2240 139 2620 571 217 698 323 2341 1189 738 1630 2 2026 263 1691 2610 631 2056 2771 878 726 2132 39 877 1775 770 2006 2046 2595 2033 2724 1163 708 1387 2261 2665 2300 1233 1123 2144 790 1048 2433 63 433 2060 2185 612 595 1942 1546 2178 1811 2779 158 808 1699 1398 1765 969 586 1585 831 1065 816 1280 615 1701 2080 998 804 1353 1512 371 1503 1416 393 18 2510 561 1295 706 2610 1467 695 494 2720 759 929 2027 2409 1108 1341 1870 11 2287 1774 1554 1112 1198 1969 1998 873 1987 1360 267 1550 2705 2323 2623 2542 680 595 752 2452 1082 2658 2681 2067 1818 2743 1359 2386 996 1177 26 19 985 1400 2283 2099 2392 1020 103 535 2226 1792 518 2877 108 2014 1304 1188 1759 2661 695 325 2260 102 2782 587 1427 1464 1758 1109 1630 1097 1793 1474 683 372 2028 252 1038 2832 2227 677 1045 1713 2036 551 1774 2010 127 1273 2043 543 1407 2430 15 466 1376 1967 1277 2608 1200 250 348 610 1866 889 2601 506 1199 1744 2340 1259 1837 1437 1882 710 294 2696 831 2425 2838 2782 1828 122 2940 2481 713 2607 1569 2777 2813 1814 2247 896 2955 1147 2593 1971 2927 1035 1873 1981 1132 380 520 1291 1980 2303 749 1379 2601 179 1434 689 153 658 1164 1610 568 1473 1047 2840 2404 2955 1247 2927 2554 2911 745 1112 1332 907 816 2090 534 2167 2100 3010 262 1835 2510 2287 2868 121 440 128 1657 1587 1402 2880 949 3022 1129 1707 1039 2201 1093 421 428 1089 624 628 2386 2477 2399 2169 2089 1005 1962 1209 2192 1721 1654 2404 10 2391 11 1758 2043 2929 874 1111 1314 199 1966 2212 473 370 2419 1358 1762 2011 2869 1538 2067 198 2504 2610 3012 1065 296 610 1849 1025 1479 448 755 1970 498 2640 1110 3026 429 3081 1394 1865 2570 2541 2299 2206 1081 2520 2098 2068 236 758 1863 3063 1076 178 2982 3040 1797 27 1624 424 2497 793 984 1199 2084 1189 2875 1465 845 1863 2477 3118 393 2180 1430 2550 214 1489 2993 2489 346 1299 2313 1271 1200 2967 1074 1406 524 2770 1853 494 2828 1331 1414 2575 660 2477 2124 1180 943 721 2215 278 99 1759 2401 2239 1648 1292 3057 2355 649 2361 3138 2142 2871 2076 2189 764 49 1378 2446 913 2999 2563 2684 128 1495 1095 1100 2350 3148 99 2133 1906 1806 3057 958 2821 2039 1156 1218 2120 3016 2318 514 594 2585 65 2358 1381 1998 1990 1849 1775 2707 3201 1043 1184 2986 1936 3178 2209 197 1872 1830 1400 2363 40 2908 1515 14 548 3145 484 2524 650 1479 1458 394 1815 2601 2483 2145 3065 2860 1576 2613 1354 2784 1060 3005 2289 1025 1879 1464 2166 1259 2022 678 1258 1655 778 2508 1904 2343 2872 1661 2352 2039 1227 2579 1993 2031 3078 1881 3072 741 1986 130 368 2654 232 396 1677 2299 524 763 999 1843 1743 1322 2588 432 2728 2749 3110 1419 352 3079 1654 2408 1042 3204 1900 2183 1332 1628 1363 1446 161 2865 1484 543 1974 1102 346 544 1522 1976 2958 127 2294 675 175 3042 2153 1788 814 2537 393 1546 2839 1017 1827 2451 896 1090 2951 1051 295 159 99 2844 727 2923 216 1829 1876 2719 17 1361 63 2957 928 1326 138 529 73 3150 2208 2289 2732 2104 2414 287 1188 393 3018 2470 181 349 418 1702 243 1496 1964 1261 1406 2939 1211 3316 552 301 586 3288 2682 395 2087 296 922 41 1204 2905 1749 225 2298 3384 873 612 2289 3240 3370 1579 2890 2695 383 2631 3388 2588 2954 755 1177 201 1618 2590 308 1740 1133 2154 184 1450 55 3132 1215 854 3265 2551 2030 3094 2584 2499 3391 120 3244 2133 2410 2953 1655 1614 3038 417 1421 2092 379 290 2550 970 78 2041 3105 2820 1646 2202 3133 1802 406 1191 377 1387 2380 2838 2962 551 2916 461 2028 3346 2961 249 1281 1153 2032 241 1077 266 852 3406 802 3015 2963 3012 2497 70 1565 1508 444 53 2268 658 1170 2890 2591 1790 36 364 2557 2371 1389