1 1 2 4 3 19 4 4 5 8 6 19 7 250 8 10 9 19 10 54 11 12 12 19 13 38 14 250 15 19 16 32 17 80 18 19 19 29 20 54 21 250 22 27 23 44 24 100 25 26 26 38 27 68 28 250 29 34 30 54 31 116 32 32 33 46 34 80 35 250 36 41 37 64 38 128 39 3002 40 54 41 91 42 250 43 48 44 72 45 139 46 1122 47 61 48 100 49 250 50 54 51 80 52 148 53 768 54 68 55 108 56 250 57 60 58 87 59 155 60 619 61 74 62 116 63 250 64 65 65 94 66 162 67 536 68 80 69 122 70 250 71 71 72 100 73 167 74 484 75 86 76 128 77 250 78 3002 79 106 80 172 81 447 82 91 83 134 84 250 85 1575 86 111 87 177 88 421 89 96 90 139 91 250 92 1122 93 116 94 181 95 401 96 100 97 144 98 250 99 900 100 120 101 184 102 385 103 104 104 148 105 250 106 768 107 124 108 188 109 372 110 9998 111 152 112 250 113 681 114 128 115 190 116 361 117 3002 118 155 119 250 120 619 121 132 122 193 123 352 124 1852 125 159 126 250 127 572 128 136 129 195 130 345 131 1380 132 162 133 250 134 536 135 139 136 198 137 338 138 1122 139 165 140 250 141 507 142 142 143 200 144 332 145 961 146 167 147 250 148 484 149 6210 150 202 151 327 152 849 153 170 154 250 155 464 156 3002 157 203 158 323 159 768 160 172 161 250 162 447 163 2039 164 205 165 319 166 707 167 175 168 250 169 433 170 1575 171 206 172 315 173 658 174 177 175 250 176 421 177 1302 178 208 179 312 180 619 181 20086 182 250 183 410 184 1122 185 209 186 309 187 586 188 5083 189 250 190 401 191 995 192 210 193 307 194 559 195 3002 196 250 197 392 198 900 199 212 200 304 201 536 202 2173 203 250 204 385 205 827 206 213 207 302 208 516 209 1728 210 250 211 378 212 768 213 214 214 300 215 499 216 1450 217 250 218 372 219 721 220 9998 221 298 222 484 223 1260 224 250 225 366 226 681 227 4542 228 296 229 470 230 1122 231 250 232 361 233 647 234 3002 235 295 236 458 237 1018 238 250 239 357 240 619 241 2275 242 293 243 447 244 935 245 250 246 352 247 594 248 1852 249 292 250 438 251 869 252 35893 253 348 254 572 255 1575 256 290 257 429 258 814 259 7401 260 345 261 553 262 1380 263 289 264 421 265 768 266 4224 267 341 268 536 269 1235 270 288 271 414 272 729 273 3002 274 338 275 521 276 1122 277 287 278 407 279 696 280 2354 281 335 282 507 283 1033 284 286 285 401 286 667 287 1953 288 332 289 495 290 961 291 14541 292 395 293 641 294 1681 295 330 296 484 297 900 298 6210 299 390 300 619 301 1483 302 327 303 473 304 849 305 4015 306 385 307 598 308 1334 309 325 310 464 311 806 312 3002 313 380 314 580 315 1217 316 323 317 455 318 768 319 2418 320 376 321 564 322 1122 323 64207 324 447 325 735 326 2039 327 372 328 549 329 1045 330 9998 331 440 332 707 333 1772 334 368 335 536 336 980 337 5526 338 433 339 681 340 1575 341 365 342 524 343 925 344 3867 345 427 346 658 347 1423 348 361 349 512 350 877 351 3002 352 421 353 637 354 1302 355 358 356 502 357 836 358 2470 359 415 360 619 361 1204 362 20086 363 493 364 800 365 2111 366 410 367 602 368 1122 369 8022 370 484 371 768 372 1852 373 405 374 586 375 1054 376 5083 377 475 378 740 379 1656 380 401 381 572 382 995 383 3757 384 468 385 714 386 1503 387 396 388 559 389 945 390 3002 391 460 392 691 393 1380 394 129587 395 547 396 900 397 2514 398 454 399 671 400 1279 401 12929 402 536 403 861 404 2173 405 447 406 652 407 1194 408 6916 409 526 410 827 411 1922 412 442 413 634 414 1122 415 4772 416 516 417 796 418 1728 419 436 420 619 421 1061 422 3671 423 507 424 768 425 1575 426 431 427 604 428 1007 429 3002 430 499 431 743 432 1450 433 27008 434 591 435 961 436 2551 437 491 438 721 439 1347 440 9998 441 578 442 919 443 2227 444 484 445 700 446 1260 447 6210 448 566 449 882 450 1983 451 477 452 681 453 1186 454 4542 455 556 456 849 457 1793 458 470 459 663 460 1122 461 3603 462 545 463 820 464 1640 465 442758 466 647 467 1067 468 3002 469 536 470 793 471 1515 472 16262 473 632 474 1018 475 2583 476 527 477 768 478 1411 479 8404 480 619 481 974 482 2275 483 519 484 746 485 1322 486 5719 487 606 488 935 489 2039 490 511 491 725 492 1246 493 4365 494 594 495 900 496 1852 497 504 498 707 499 1180 500 3548 501 583 502 869 503 1700 504 35893 505 689 506 1122 507 3002 508 572 509 840 510 1575 511 12162 512 673 513 1071 514 2610 515 562 516 814 517 1469 518 7401 519 658 520 1026 521 2317 522 553 523 790 524 1380 525 5359 526 644 527 985 528 2088 529 544 530 768 531 1302 532 4224 533 631 534 949 535 1905 536 536 537 748 538 1235 539 3502 540 619 541 916 542 1755 543 20086 544 729 545 1175 546 3002 547 607 548 886 549 1630 550 9998 551 712 552 1122 553 2635 554 596 555 858 556 1524 557 6712 558 696 559 1075 560 2354 561 586 562 833 563 1433 564 5083 565 681 566 1033 567 2133 568 577 569 810 570 1355 571 4110 572 667 573 995 574 1953 575 47712 576 788 577 1286 578 3463 579 654 580 961 581 1805 582 14541 583 768 584 1225 585 3002 586 641 587 929 588 1681 589 8662 590 750 591 1171 592 2656 593 630 594 900 595 1575 596 6210 597 733 598 1122 599 2388 600 619 601 874 602 1483 603 4865 604 717 605 1079 606 2173 607 608 608 849 609 1404 610 4015 611 702 612 1039 613 1998 614 24518 615 827 616 1334 617 3429 618 688 619 1004 620 1852 621 11713 622 806 623 1272 624 3002 625 674 626 971 627 1728 628 7754 629 786 630 1217 631 2675 632 662 633 941 634 1622 635 5827 636 768 637 1167 638 2418 639 650 640 913 641 1531 642 4688 643 751 644 1122 645 2210 646 64207 647 888 648 1450 649 3935 650 735 651 1082 652 2039 653 17168 654 864 655 1380 656 3401 657 721 658 1045 659 1895 660 9998 661 842 662 1317 663 3002 664 707 665 1011 666 1772 667 7097 668 822 669 1260 670 2692 671 693 672 980 673 1667 674 5526 675 803 676 1210 677 2445 678 681 679 951 680 1575 681 4542 682 785 683 1164 684 2244 685 29714 686 925 687 1494 688 3867 689 768 690 1122 691 2076 692 13561 693 900 694 1423 695 3375 696 753 697 1084 698 1935 699 8848 700 877 701 1359 702 3002 703 738 704 1050 705 1813 706 6599 707 856 708 1302 709 2708 710 724 711 1018 712 1708 713 5283 714 836 715 1251 716 2470 717 88836 718 988 719 1617 720 4419 721 818 722 1204 723 2275 724 20086 725 961 726 1536 727 3808 728 800 729 1161 730 2111 731 11418 732 935 733 1464 734 3353 735 784 736 1122 737 1972 738 8022 739 912 740 1400 741 3002 742 768 743 1087 744 1852 745 6210 746 889 747 1342 748 2721 749 754 750 1054 751 1747 752 5083 753 869 754 1289 755 2493 756 35893 757 1023 758 1656 759 4314 760 849 761 1242 762 2303 763 15560 764 995 765 1575 766 3757 767 831 768 1199 769 2143 770 9998 771 969 772 1503 773 3334 774 814 775 1159 776 2006 777 7401 778 945 779 1438 780 3002 781 798 782 1122 783 1888 784 5896 785 922 786 1380 787 2734 788 129587 789 1089 790 1784 791 4915 792 900 793 1327 794 2514 795 23345 796 1058 797 1693 798 4224 799 880 800 1279 801 2330 802 12929 803 1029 804 1612 805 3711 806 861 807 1235 808 2173 809 8988 810 1002 811 1540 812 3316 813 844 814 1194 815 2039 816 6916 817 976 818 1475 819 3002 820 827 821 1157 822 1922 823 5639 824 953 825 1416 826 2746 827 43361 828 1122 829 1819 830 4772 831 931 832 1362 833 2533 834 17727 835 1091 836 1728 837 4145 838 910 839 1314 840 2354 841 11210 842 1061 843 1647 844 3671 845 891 846 1269 847 2201 848 8233 849 1033 850 1575 851 3300 852 872 853 1228 854 2069 855 6528 856 1007 857 1510 858 3002 859 209991 860 1190 861 1953 862 5423 863 983 864 1450 865 2756 866 27008 867 1155 868 1852 869 4649 870 961 871 1397 872 2551 873 14541 874 1122 875 1761 876 4076 877 939 878 1347 879 2377 880 9998 881 1092 882 1681 883 3635 884 919 885 1302 886 2227 887 7647 888 1064 889 1608 890 3286 891 900 892 1260 893 2097 894 6210 895 1037 896 1543 897 3002 898 52570 899 1222 900 1983 901 5240 902 1013 903 1483 904 2766 905 20086 906 1186 907 1883 908 4542 909 989 910 1429 911 2568 912 12488 913 1153 914 1793 915 4015 916 968 917 1380 918 2398 919 9098 920 1122 921 1713 922 3603 923 947 924 1334 925 2252 926 7179 927 1094 928 1640 929 3273 930 442758 931 1292 932 2124 933 5944 934 1067 935 1575 936 3002 937 31157 938 1253 939 2012 940 5083 941 1041 942 1515 943 2775 944 16262 945 1217 946 1912 947 4448 948 1018 949 1461 950 2583 951 11055 952 1183 953 1823 954 3960 955 995 956 1411 957 2418 958 8404 959 1152 960 1743 961 3574 962 974 963 1365 964 2275 965 6797 966 1122 967 1671 968 3261 969 64207 970 1322 971 2149 972 5719 973 1095 974 1605 975 3002 976 22663 977 1283 978 2039 979 4946 980 1069 981 1546 982 2783 983 13837 984 1246 985 1940 986 4365 987 1045 988 1491 989 2597 990 9998 991 1212 992 1852 993 3911 994 1022 995 1441 996 2436 997 7851 998 1180 999 1772 1000 3548