2
1000 1000
866 666 454 218 928 436 128 534 332 978 752 568 54 418 776 538 200 210 446 556 766 822 44 150 190 102 862 372 966 472 558 558 578 126 186 966 892 226 128 506 560 188 852 806 302 270 800 202 818 30 592 568 750 512 18 544 348 876 602 158 888 942 796 106 872 836 686 552 150 72 358 574 754 616 50 338 456 76 172 122 746 372 328 214 142 612 738 534 280 778 806 638 686 254 554 724 104 112 422 456 184 242 352 146 32 228 78 944 560 650 100 714 146 866 408 44 984 94 996 32 524 886 938 138 502 970 292 830 220 606 658 734 200 938 780 478 828 392 30 708 328 424 272 288 706 692 286 152 298 102 498 600 760 894 794 490 284 154 120 672 724 552 62 372 166 588 256 834 608 962 88 320 876 184 840 572 232 946 676 932 550 636 946 690 490 844 418 16 354 592 532 122 736 268 570 974 706 222 680 252 736 162 332 914 628 292 806 44 406 496 404 232 26 844 534 566 960 436 406 568 672 318 334 228 964 386 652 996 140 154 670 280 262 638 966 834 578 976 722 186 832 668 40 920 998 26 346 42 756 840 992 402 552 664 222 418 202 626 392 10 476 496 890 706 798 712 986 144 448 708 776 44 126 632 38 794 730 74 132 130 886 850 930 648 66 356 76 806 400 312 796 468 548 194 680 294 948 58 970 294 184 590 312 626 220 16 384 344 518 512 924 226 420 942 724 874 790 666 892 842 180 414 834 722 804 350 730 546 538 526 994 964 144 6 606 742 182 844 484 618 966 960 816 948 784 750 460 696 308 38 192 64 358 244 430 704 140 10 782 322 714 734 764 686 770 526 298 372 760 318 920 260 454 308 920 986 322 720 446 198 842 348 32 156 218 166 504 302 824 326 424 694 262 406 838 216 464 360 676 106 786 530 434 122 652 364 34 162 910 508 478 430 398 58 830 328 696 502 106 122 348 356 226 64 86 222 960 200 806 894 346 152 322 414 552 418 94 48 212 682 480 584 420 792 938 12 954 666 92 366 312 910 710 298 458 304 110 534 688 428 148 316 162 4 404 6 730 870 962 412 754 446 492 598 106 820 896 700 594 48 180 746 256 442 58 436 552 510 858 734 716 250 78 828 280 444 584 344 602 182 658 310 954 314 864 542 936 642 314 852 88 888 234 568 944 76 244 932 200 218 770 812 690 948 958 336 464 94 450 444 570 348 432 724 308 216 364 70 380 274 816 210 966 210 60 14 96 194 190 914 50 140 142 600 434 442 854 282 956 686 758 796 758 394 274 794 436 692 482 732 82 684 408 724 266 704 292 988 522 586 496 742 92 150 384 2 372 900 790 426 604 810 768 602 100 914 784 950 834 834 904 790 498 856 872 200 664 488 794 736 360 92 412 82 622 498 188 28 444 384 222 26 614 734 892 248 816 474 938 866 674 988 412 974 46 530 182 68 632 974 322 48 722 810 560 882 132 930 712 594 154 732 436 728 142 594 780 886 894 844 536 588 926 166 394 654 72 190 830 480 978 852 788 422 820 50 292 636 18 500 38 48 810 60 526 58 300 96 614 876 256 490 594 770 618 386 236 736 352 496 470 538 886 912 978 366 50 152 350 928 478 132 802 280 982 390 794 984 848 348 990 8 440 502 66 732 664 844 746 14 622 474 54 636 112 746 416 478 536 208 678 516 370 626 340 178 272 964 558 770 174 518 102 792 260 784 34 654 982 586 962 932 786 314 258 970 550 936 728 766 868 992 274 36 230 858 98 600 956 520 248 184 812 78 80 902 18 268 818 934 848 720 266 600 920 14 566 590 596 208 98 130 572 924 852 194 380 442 280 472 856 156 406 222 188 338 970 440 436 876 322 442 370 412 744 92 874 946 122 212 500 496 812 740 386 526 438 488 924 628 116 460 822 64 404 60 644 890 150 758 114 390 304 484 88 82 196 658 480 110 744 524 144 696 150 288 116 944 570 366 902 588 944 626 956 462 370 434 816 346 924 90 748 302 62 960 122 780 178 346 472 894 894 146 690 432 366 468 34 110 664 598 524 80 248 800 250 182 224 786 534 342 426 630 790 300 24 102 270 828 162 722 770 782 770 772 238 818 308 946 614 306 754 44 640 672 864 778 48 810 4 534 982 494 8 214 808 766 838 174 774 986 632 988 536 292 398 796 108 492 630 366 384 844 588 102 974 298 858 686 228 966 970 524 784 110 844 378 216 252 102 734 872 130 488 656 670 114 692 302 132 488 258 944 12 670 446 614 752 516
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
