3000 23
0 1 1 3 4 5 4 3 7 8 5 3 10 8 5 8 5 5 17 17 8 3 18 9 24 19 24 7 17 1 3 17 22 23 13 4 21 3 5 38 18 33 35 34 5 15 14 43 32 18 45 50 38 9 53 46 12 38 4 55 39 59 18 44 4 39 33 41 44 67 57 69 44 48 1 43 75 51 55 27 70 12 77 78 43 31 50 45 13 84 69 89 55 43 65 17 87 68 72 88 23 13 72 53 49 47 2 43 106 39 73 83 87 93 13 35 91 78 83 24 90 15 37 78 60 29 108 106 32 129 56 97 42 24 129 38 134 15 23 90 139 44 142 79 121 102 25 7 68 12 55 27 117 136 122 78 114 70 24 3 25 22 8 109 30 66 155 158 77 25 161 112 63 46 89 26 79 95 137 88 27 24 173 129 29 44 48 35 146 166 159 23 134 127 149 26 174 179 17 130 128 85 60 107 179 162 25 173 103 57 14 180 38 153 8 147 87 59 2 136 124 46 165 140 214 173 99 5 26 206 59 176 128 50 192 211 150 212 76 104 61 20 21 148 33 193 191 224 135 233 44 58 226 214 111 99 71 250 248 129 134 100 84 171 19 116 3 30 74 20 126 165 105 135 235 205 179 137 241 248 233 38 269 66 55 279 195 278 248 226 149 135 125 229 134 4 228 265 178 241 248 178 268 161 110 127 24 274 286 3 78 6 253 90 136 45 12 111 169 39 197 225 15 3 211 31 47 3 161 232 70 53 234 331 12 30 144 50 174 294 3 270 45 89 67 194 316 110 200 148 3 66 202 104 93 220 345 252 154 164 317 145 196 58 192 344 311 217 272 102 355 197 185 123 301 271 136 367 87 159 335 365 372 289 303 178 376 373 310 339 351 263 224 270 146 72 221 148 367 136 160 61 330 34 279 81 323 359 310 194 327 215 367 84 324 240 50 265 88 190 409 203 380 71 304 91 182 166 136 148 214 337 420 257 104 8 163 95 274 288 228 94 176 93 119 34 113 411 228 209 407 66 450 337 230 328 440 328 412 379 336 329 68 115 207 141 346 58 233 206 297 317 127 56 321 256 403 246 156 226 334 322 193 136 443 224 326 401 463 259 318 300 111 363 362 161 96 189 492 491 59 359 138 135 372 504 460 257 192 284 113 40 351 478 111 138 75 462 178 112 82 45 93 334 477 397 35 156 444 180 258 386 197 206 111 431 304 132 448 41 27 409 100 140 513 254 425 184 519 382 438 509 155 404 483 388 298 171 334 277 28 127 345 302 520 187 147 88 331 514 423 428 413 320 370 387 277 390 353 81 97 453 145 454 194 158 216 496 499 458 33 73 135 117 268 106 277 486 57 333 241 69 410 485 363 91 211 76 477 288 302 293 570 400 515 482 358 510 74 177 137 309 282 93 81 31 313 234 128 234 16 306 277 518 536 460 86 632 37 132 433 553 396 100 318 221 141 530 294 592 550 174 239 4 383 164 7 189 48 656 451 425 448 520 529 132 587 154 525 561 227 639 140 272 524 303 458 561 349 418 333 470 397 478 211 685 545 11 143 510 74 431 683 50 192 27 43 27 206 421 24 608 346 318 57 184 406 462 705 142 285 679 480 225 224 585 98 235 139 338 90 342 666 317 211 498 582 586 159 228 695 13 246 579 271 263 30 659 458 471 465 420 26 547 606 666 329 212 34 271 570 370 748 227 388 77 354 606 235 404 547 756 491 487 68 619 330 638 114 376 304 470 229 248 553 476 395 88 601 290 669 664 669 402 462 392 650 439 346 110 595 352 254 622 446 87 659 85 230 128 289 51 592 460 649 580 428 100 598 484 146 144 104 446 325 280 410 283 99 530 724 425 13 248 56 533 455 121 828 323 758 729 823 239 735 372 431 773 811 448 627 432 65 738 296 295 8 387 106 212 614 680 630 467 221 336 533 290 355 525 571 379 836 773 851 843 461 697 466 389 606 470 558 547 722 264 746 615 764 243 96 249 492 492 285 34 331 410 863 771 257 527 678 167 55 219 119 847 609 148 479 519 510 37 400 801 633 537 899 498 873 260 114 82 820 410 865 397 269 84 384 390 340 259 619 422 253 342 339 166 189 791 201 394 815 110 827 875 170 923 915 692 421 824 31 100 613 655 656 122 466 515 674 454 165 436 123 125 650 87 776 734 352 37 219 499 811 195 664 775 400 172 391 609 397 745 51 581 537 337 713 937 357 511 795 44 316 586 280 80 754 478 935 421 212 974 964 650 528 772 594 465 84 276 801 200 962 168 319 350 582 10 476 687 556 183 167 650 278 83 1009 480 548 333 91 875 181 163 652 911 29 360 424 112 296 883 795 523 701 401 793 802 411 718 484 55 807 324 576 275 71 292 101 186 199 776 474 477 940 895 735 685 736 728 662 429 400 534 434 269 865 577 765 469 1073 3 53 916 709 244 437 13 1074 626 913 251 900 626 126 895 506 159 221 53 1049 891 216 490 336 661 370 690 867 813 732 1034 717 928 994 592 312 633 291 956 786 364 36 401 435 804 949 469 979 1054 768 1059 144 645 10 815 922 1037 270 614 1071 762 333 353 864 965 771 635 382 327 734 810 66 33 187 121 12 490 159 51 1013 348 929 1094 675 944 750 894 472 562 981 956 279 684 583 336 870 1139 371 879 431 142 188 160 810 329 280 331 731 287 199 498 637 286 127 229 836 522 1148 519 916 473 790 444 948 17 325 1055 422 434 991 1025 603 743 571 992 141 146 667 857 280 231 590 1159 284 1186 1058 1144 637 266 1102 1154 140 261 486 1217 168 921 661 546 474 40 534 407 801 1167 360 302 352 490 131 383 118 112 1020 659 289 243 730 131 908 101 994 18 484 1237 835 1056 725 248 1124 298 1004 402 546 485 484 497 1060 743 1120 1142 430 330 596 595 70 271 878 1070 505 1156 685 554 1224 505 552 420 576 551 85 1064 1054 148 169 401 940 207 298 229 851 614 621 746 1202 34 514 528 342 986 621 956 104 137 189 638 257 498 67 722 928 721 464 486 445 476 789 146 1224 325 119 530 387 559 454 1217 645 38 188 67 1006 1140 667 1060 969 997 28 613 1307 1219 56 713 987 1100 1348 934 1317 1161 725 182 239 1280 123 152 1258 260 924 158 1365 343 510 18 819 725 164 262 47 636 670 897 279 1186 513 1158 710 722 330 516 1275 1196 570 430 814 659 641 862 1203 1280 227 778 120 390 603 93 1115 978 1152 55 832 767 1410 1036 898 567 666 952 272 989 1286 294 95 1375 630 300 728 790 1189 740 842 637 82 978 743 1030 1111 1123 781 349 746 1441 676 869 308 1295 752 1220 437 774 179 914 919 719 212 539 136 806 26 1013 668 386 47 30 227 498 138 475 564 1233 1165 56 250 1129 969 854 1094 1105 566 729 1422 1152 979 819 1081 760 1148 182 789 878 116 343 694 1269 715 259 1472 1117 335 1188 322 1289 774 799 1029 385 1295 758 1137 653 1202 771 1152 1221 1204 766 1013 1158 1138 1307 677 135 970 1025 1244 83 63 521 322 261 1371 1007 503 144 329 628 498 958 217 1094 415 541 947 425 130 821 1252 450 1388 17 312 466 1412 1108 1223 355 267 1554 240 201 794 1014 479 992 533 1320 135 20 1523 517 987 1511 465 510 115 51 280 403 1125 1097 901 255 982 358 643 293 491 294 697 400 398 1016 1409 757 359 1424 613 1073 258 1184 295 1464 1095 1045 497 288 555 884 2 1011 824 470 749 1209 617 554 1242 1402 922 848 564 545 1535 387 363 1270 105 122 508 725 427 1088 517 197 184 1181 152 231 1327 284 506 956 422 739 437 1072 1343 475 1366 294 1210 44 1010 389 1299 1005 1624 375 1349 227 546 242 167 1500 62 754 1190 935 716 494 168 809 59 72 886 1273 679 764 741 756 731 1039 1626 527 902 1493 1241 568 1566 273 629 372 720 1168 325 1145 29 537 1484 74 1093 1106 621 98 1580 861 862 1702 1580 315 558 884 712 1394 1307 703 1096 38 102 614 647 900 492 909 612 185 227 857 450 558 1356 289 838 1433 192 803 1148 461 529 1692 563 28 107 687 1476 846 890 494 1283 792 593 1506 1052 1356 658 375 1397 1197 856 1488 207 141 1141 1140 1400 1313 1543 21 689 998 1260 1399 1443 996 251 721 1051 47 597 165 1569 688 586 105 1728 135 155 55 1090 709 1340 465 1262 417 1427 1446 1488 321 827 758 1130 1339 761 1695 1737 1073 309 546 1447 1122 290 119 784 938 37 950 1051 914 901 1322 1018 1284 1211 302 944 1823 227 1618 195 1785 1032 1803 1407 401 1484 50 1148 172 1284 758 1104 1467 427 639 1684 1377 714 1556 1471 1154 1052 285 997 1035 516 1074 395 1338 467 700 1539 155 808 1623 1137 1342 405 699 1212 1367 1650 472 5 1669 262 705 1048 1558 124 121 1329 985 1880 1860 561 1596 62 930 223 374 1885 356 788 1821 463 1166 1269 923 110 766 104 1469 1615 69 1662 25 709 554 1558 297 1425 1787 486 1844 1580 1266 922 1049 1592 1730 1254 1129 1606 169 641 98 1205 1551 789 1128 1924 1476 29 1801 482 877 331 640 1675 1595 448 1811 137 441 153 1799 519 371 1 135 818 1657 198 1148 78 114 426 502 1768 1476 1726 234 1129 756 1125 1599 1281 589 1379 958 1619 180 237 223 658 215 1427 1050 1501 270 343 683 1060 1814 437 547 1221 1702 1312 698 790 1797 1817 58 216 563 504 815 1311 1993 361 792 425 1664 1127 1804 985 1491 108 1559 756 1903 726 1716 382 234 1951 1658 1866 369 1830 963 910 899 998 1162 91 571 192 1547 1294 2025 743 653 1124 657 1814 1492 977 1433 1755 739 2035 1772 1678 862 426 1086 210 23 98 709 276 1207 1528 386 256 1534 520 845 964 1146 329 166 591 1828 1348 987 670 568 2042 1765 132 609 1321 67 355 1592 1347 1424 227 1526 875 75 954 821 1673 843 2062 1058 1367 1323 1401 1206 1524 1372 1305 36 2004 1948 1380 1726 14 363 973 860 1238 1869 749 1585 2065 669 2052 496 1978 840 1565 1957 66 983 178 1989 1807 373 503 1029 1986 811 1269 762 1198 1245 1011 2067 1662 1895 1856 473 1015 1855 1183 1095 71 1176 877 19 1407 222 2130 236 691 516 1180 930 79 863 1061 1560 1991 1096 203 260 1667 760 375 2138 1429 2001 1110 948 1170 1506 297 1918 1297 1502 1177 739 2012 1880 1892 1860 531 1863 258 878 1211 1383 1619 500 326 98 1703 998 2115 1242 2008 1373 610 1462 2104 888 761 184 1899 537 1929 1152 353 1243 1256 1531 1808 656 1208 33 2058 730 1605 619 963 1462 143 49 17 620 753 1373 412 1683 1730 1308 1476 596 1943 486 1777 945 1952 1305 981 929 817 738 1430 653 404 296 506 1247 682 292 290 1089 1859 1592 1966 1498 2071 1639 370 726 916 80 1017 402 1900 836 1796 1123 362 1075 698 2238 435 790 349 1713 2257 1999 444 894 493 1756 38 373 2042 561 2150 428 696 2186 2163 1056 1348 192 396 55 2199 1163 69 716 888 2114 688 761 19 132 632 341 2042 909 1923 1259 1882 1533 3 993 1258 2084 2285 1441 1336 475 197 143 2084 1883 1774 1575 130 6 1991 977 1111 1824 1835 1442 437 1574 2 614 2262 885 684 1674 612 481 518 632 553 2101 1712 653 1386 1443 250 860 65 852 2141 1915 2050 1100 84 703 1068 38 1536 543 2185 1718 1687 1423 563 1788 1559 2372 2248 282 1307 2044 2130 1799 419 925 506 749 790 816 310 42 1133 2045 1143 677 46 1239 1703 2200 740 2060 2299 548 1152 1427 1270 1289 840 16 510 894 2398 2313 2213 651 1101 413 387 601 1680 538 1685 1206 2257 1383 1371 1807 1781 1387 2292 2333 479 123 1472 1494 451 1438 2161 2152 878 1195 582 2425 1311 1639 2299 828 555 2178 125 626 228 1348 378 1793 1353 828 1762 532 47 403 984 247 1641 2281 1898 221 2182 132 266 2429 510 1895 2279 1983 2037 1326 1797 688 1030 251 739 577 893 669 199 1953 1954 1491 325 1841 1991 1452 1245 2036 2146 1834 2125 1816 582 1108 1125 170 440 2386 562 1474 335 1795 2319 1651 580 2212 780 1798 639 1920 958 2354 1572 2166 1512 438 1720 778 781 1380 1572 368 1516 2032 1778 537 1907 130 1880 661 645 2295 872 1108 3 1973 688 357 1250 893 118 822 168 2275 746 2550 2104 799 1268 746 2414 733 978 2508 954 1953 2546 1584 176 171 1371 2334 2481 760 893 424 2066 1132 102 2178 1634 2450 960 927 1904 1632 303 1365 2419 1758 398 1411 625 984 2211 1069 2198 1494 2535 1447 718 2007 802 2316 2198 1169 34 1361 2084 2514 1262 2230 838 317 262 780 1346 2610 2361 667 1021 1238 1189 2132 1874 2032 370 521 1048 1388 1151 2519 2005 1083 939 2219 2059 1771 535 438 1202 419 2227 1209 1941 1765 1784 2434 812 393 1030 1520 1210 842 1802 1251 1151 1396 1742 2659 1251 827 1720 1085 1328 946 649 484 1711 2422 805 336 2025 1762 814 1404 2054 1209 1616 2494 493 2166 31 2070 1668 2466 421 1556 1956 1204 768 2092 737 1207 259 2597 1357 855 850 153 846 2631 1084 1287 1074 1326 627 1173 673 303 1542 516 2365 481 2293 1444 1788 216 2409 2315 1512 1164 1544 1144 2041 1248 2086 2637 1608 2096 1124 1159 949 821 1814 1638 336 1341 1285 1170 1089 731 2647 489 1568 1150 417 600 908 2383 1256 686 652 924 2424 2250 490 2377 2118 1283 2481 607 54 2752 577 991 880 722 869 1535 403 1996 96 2403 1933 2576 2153 1512 1377 260 2151 1272 560 596 1981 660 808 1860 829 2546 2173 1021 1680 1262 775 562 33 832 297 1687 2494 68 981 208 1805 1537 2146 2532 987 553 955 273 2029 1811 835 740 385 2198 2604 2570 1129 2602 2746 5 2790 605 1845 2037 1873 868 149 65 2079 121 231 1075 1877 1588 2117 2733 2757 1208 2549 2061 1377 1729 1822 101 2802 2425 2725 2730 2416 82 1324 1228 2146 2699 780 2197 501 1842 798 443 400 1278 143 2724 2620 1115 1867 1995 2756 767 2484 2155 568 1921 1773 1166 568 70 1062 107 258 668 49 497 252 2536 1859 2521 577 1143 6 1715 2878 1677 2789 770 1965 1809 2390 1199 6 1734 2076 1407 2201 2301 2810 2148 1985 209 1859 1149 962 535 1463 558 2289 2899 184 1302 1196 1854 2872 195 1862 296 2528 554 556 1864 2688 566 2303 1377 2861 1401 555 2491 583 2809 2840 1909 544 2296 2419 974 1136 945 2573 345 1567 2101 631 745 861 2797 1577 597 2202 116 2002 2900 1456 357 428 1161 2078 793 2083 1715 2402 988 869 1938 1578 81 856 608 1036 2405 279 1699 1040 2239 978 1790 632 2131 383 1610 1028 1344 1277 1827 1212 1157