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