4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
100 304 166 849 478 770 991 42 114 85 425 799 91 333 958 401 988 684 709 513 737 672 156 994 575 79 707 282 238 892 479 985 196 996 185 25 766 175 419 231 259 843 30 349 175 987 102 162 23 810 27 111 833 182 104 408 260 162 41 850 54 519 186 601 867 370 625 632 544 395 214 154 238 243 854 764 582 955 278 956 117 304 66 949 485 521 708 96 682 749 945 87 267 482 39 485 851 16 116 746 410 
1000 22 84 275 327 364 538 26 364 29 386 545 955 715 965 404 415 903 942 402 150 718 605 969 280 574 719 323 883 721 821 631 374 905 257 700 620 795 725 984 823 462 880 777 176 845 532 943 99 473 344 248 190 948 568 822 873 287 496 755 7 317 738 732 573 994 432 192 140 508 527 962 970 407 91 497 603 974 439 701 447 134 300 988 433 868 161 306 506 657 412 864 325 501 595 249 847 378 440 986 886 967 300 207 725 742 703 327 715 494 379 513 627 678 853 412 897 365 717 402 21 480 265 697 981 212 945 827 589 385 164 826 703 463 384 427 556 439 105 271 932 483 135 910 160 987 321 57 352 37 810 724 869 427 421 849 638 365 27 578 101 190 756 155 5 139 933 560 577 37 182 860 519 317 770 679 303 90 87 6 479 896 730 347 674 502 547 663 866 573 241 319 114 348 825 470 486 758 30 63 794 211 922 313 879 43 343 182 485 781 539 315 28 268 661 702 769 559 364 987 483 956 657 596 303 481 66 141 238 447 555 32 9 476 696 888 871 390 421 355 170 959 669 549 579 681 602 347 239 966 685 73 273 341 668 928 822 85 68 59 531 622 442 892 449 489 779 319 878 199 25 399 509 693 948 87 725 549 434 315 866 470 387 139 811 407 66 632 491 485 42 374 106 836 265 554 324 43 225 202 593 249 600 453 294 547 540 18 448 325 333 313 794 719 803 604 477 220 587 968 704 981 341 809 816 957 715 139 351 939 340 295 539 292 747 832 190 286 850 637 962 534 302 756 604 456 711 81 676 650 400 379 630 92 540 445 48 606 935 750 544 627 44 434 918 790 266 459 428 467 96 389 352 749 496 955 204 207 387 879 856 786 610 837 877 501 281 924 106 215 673 1 193 68 434 110 858 51 569 637 869 16 25 220 116 873 175 319 79 561 550 286 347 511 122 575 363 754 851 820 320 523 172 513 943 605 974 152 8 542 788 876 909 164 96 376 36 622 47 114 182 948 751 880 458 872 455 172 625 305 991 945 179 162 809 121 118 782 624 125 324 411 353 584 575 800 960 962 421 358 428 954 305 178 834 762 402 640 285 26 296 275 322 474 436 130 947 905 912 922 382 587 333 734 522 259 533 833 220 305 190 647 258 494 177 91 607 578 82 891 955 377 165 277 203 952 758 501 209 21 422 590 607 106 675 481 364 559 313 936 863 503 582 120 348 110 563 955 687 644 845 642 373 362 270 927 665 379 427 873 400 200 814 358 306 488 838 669 46 151 956 260 5 538 380 704 999 294 658 686 289 855 679 661 568 300 587 232 678 365 457 429 565 270 787 222 758 624 242 155 126 198 415 482 87 146 186 85 439 843 122 79 49 152 740 616 451 678 200 481 395 656 909 311 925 47 532 34 23 125 541 148 322 955 982 408 452 167 845 242 361 966 320 410 118 411 377 920 441 576 752 835 231 13 497 508 59 380 541 81 504 81 581 826 387 562 585 838 728 429 431 440 747 751 849 216 513 578 135 953 153 239 139 736 251 987 243 309 366 783 390 870 216 970 47 602 531 631 792 610 60 222 49 806 324 250 21 837 827 507 141 331 745 280 66 995 266 308 656 984 443 397 853 658 366 899 611 248 881 754 209 940 328 609 97 651 858 469 839 36 328 980 719 424 611 784 419 228 444 426 211 886 822 415 895 539 665 857 138 546 611 346 837 938 954 934 940 164 754 779 551 433 110 269 857 720 405 627 299 200 52 862 85 873 628 331 763 293 187 900 838 797 245 674 86 550 959 26 65 65 804 968 497 265 588 353 336 992 331 634 543 382 847 627 606 475 309 368 119 496 267 956 644 863 981 730 765 292 107 181 708 262 148 204 526 736 909 861 79 239 846 622 973 45 600 578 519 261 298 637 756 564 944 751 779 276 832 543 919 938 75 626 199 223 182 76 310 90 936 740 680 134 713 4 178 665 582 48 925 879 36 680 794 331 782 572 606 614 466 877 551 541 502 102 115 683 177 776 124 465 515 156 950 228 159 127 244 92 526 168 322 913 199 468 243 980 391 200 593 857 76 496 749 578 597 863 612 125 638 736 589 504 243 538 83 401 16 326 845 893 493 166 805 43 633 47 23 24 599 615 232 674 462 332 603 58 546 567 183 535 654 123 38 896 661 121 648 28 798 492 921 643 658 725 685 642 124 707 17 722 674 248 747 135 579 702 545 124 268 79 10 921 201 48 816 213 520 463 241 669 307 161 311 964 885 996 957 8 54 974 729 
1000 399 326 811 452 683 315 631 211 54 305 965 938 1000 619 835 955 298 50 848 839 364 22 379 263 180 563 230 55 120 653 102 519 978 265 322 12 579 952 223 984 257 539 921 256 158 107 562 807 156 409 997 871 783 375 486 962 289 715 368 409 719 470 279 48 86 600 411 664 904 985 999 512 524 919 119 33 25 680 839 533 441 188 755 223 562 240 536 203 306 903 963 376 724 241 423 809 192 834 824 447 818 822 958 693 740 76 725 117 108 916 1 548 103 755 770 16 347 305 218 652 559 532 380 283 124 802 91 316 987 915 114 157 736 72 849 828 499 574 296 606 841 648 153 943 402 274 310 100 578 880 104 489 411 483 771 535 284 213 202 623 127 315 779 215 738 627 394 237 552 41 842 392 688 347 686 441 620 996 541 550 875 644 38 637 126 808 171 761 20 724 383 499 391 513 65 128 140 458 716 43 498 558 435 185 904 120 977 875 115 517 424 341 512 461 978 989 620 500 750 992 576 484 842 966 349 906 445 488 363 161 530 212 718 316 748 973 436 724 847 902 593 623 595 104 435 924 93 55 775 194 398 350 29 239 667 377 144 112 216 858 272 98 421 341 413 168 313 200 243 511 454 835 485 400 291 920 323 383 326 97 928 723 799 308 961 465 37 456 576 252 313 199 701 85 539 466 252 203 665 494 714 470 681 550 869 971 469 191 705 794 640 984 868 438 291 180 254 679 635 182 931 299 380 983 383 919 448 986 121 465 832 186 934 512 736 803 834 556 345 890 350 336 873 569 125 515 749 379 546 383 560 828 682 291 810 416 209 258 402 330 722 233 867 655 96 602 809 281 510 506 170 859 841 394 779 966 260 527 696 805 910 607 632 943 897 442 710 106 699 111 787 772 695 5 426 790 959 587 422 468 92 591 678 284 984 456 249 244 983 296 48 892 902 32 186 799 473 895 256 523 358 394 294 52 398 71 194 356 657 615 175 100 206 852 384 541 308 984 136 290 280 536 533 533 567 718 683 39 964 938 561 321 683 854 373 433 276 918 140 933 532 315 384 89 166 119 630 473 103 765 114 734 300 998 618 866 715 301 256 31 590 816 351 273 21 75 57 297 992 196 581 524 510 316 964 28 435 593 852 889 710 966 622 361 963 591 579 30 891 834 412 481 2 762 105 22 837 161 670 828 356 602 703 218 918 667 245 704 611 96 592 320 413 565 33 376 155 611 757 46 444 168 878 797 281 982 171 117 494 840 297 201 794 351 418 711 17 662 414 628 110 5 299 522 921 331 249 75 293 357 472 89 876 349 885 157 682 55 625 175 247 921 376 40 624 145 750 640 159 515 619 268 871 270 141 791 952 742 865 245 98 689 685 974 37 569 482 71 976 106 245 222 379 972 261 2 117 362 993 627 876 964 246 98 233 386 888 536 127 104 132 577 792 816 550 181 737 383 251 712 488 847 285 866 819 545 219 287 258 212 265 485 175 510 582 759 895 469 646 374 924 778 950 716 945 851 248 681 233 498 744 72 344 28 938 514 924 508 152 181 719 416 17 245 925 598 355 172 418 1 545 342 130 846 409 74 48 656 107 280 153 850 351 848 878 640 714 153 148 865 686 218 633 702 815 557 300 169 728 717 521 624 410 650 821 818 724 868 473 182 499 977 31 850 177 260 841 890 413 340 106 450 558 738 151 372 647 802 892 726 519 413 350 280 414 170 98 489 390 922 670 888 899 701 737 75 312 930 316 76 269 421 525 178 511 28 901 157 829 793 882 699 557 231 979 970 753 76 459 142 997 128 381 247 180 470 673 844 399 988 919 19 761 796 197 271 823 97 427 651 241 308 350 149 891 328 119 995 755 929 488 103 408 868 350 940 337 22 783 735 362 53 106 122 848 302 392 22 750 170 25 343 477 374 491 719 53 961 713 159 889 552 261 649 420 610 588 108 984 370 195 345 774 300 466 974 601 209 995 702 378 19 44 206 744 887 925 148 847 989 306 736 541 567 384 960 528 323 67 511 44 261 855 817 560 672 790 512 880 137 566 609 507 609 815 251 495 739 398 694 727 56 781 267 622 164 578 149 838 997 12 881 609 218 697 521 890 839 32 121 975 949 82 833 558 896 83 404 986 833 449 712 888 229 331 861 744 260 361 581 256 372 461 217 590 510 737 831 348 120 303 674 69 384 506 978 631 941 733 616 125 182 680 364 410 10 224 154 621 584 734 877 308 547 93 249 56 181 79 755 300 733 780 368 469 637 697 99 577 430 
10 2 1 2 1 2 1 2 1 2 1
10 3 3 3 3 3 3 3 3 3 3
0