9
1 2 1 2
1 1 1 2
1 1 1 3
1 2 2 6
1 1 1 5
1 2 3 8
1 2 2 6
1 1 3 3
1 2 2 7
1 2 2 6
1 1 2 8
1 2 1 9
1 2 2 6
1 2 1 9
1 1 2 8
50 200 50 1000
27 2 174 416
32 29 843 927
24 45 670 837
42 25 449 810
31 45 899 989
43 10 568 820
17 48 255 732
20 47 380 990
7 33 255 620
14 39 475 782
19 30 84 491
33 5 998 999
49 26 355 377
6 7 395 920
22 43 863 896
26 38 247 675
44 33 753 921
8 10 490 686
17 18 856 992
20 40 361 954
39 40 903 982
11 29 567 693
17 29 931 947
26 13 505 505
13 37 513 518
11 7 835 981
25 40 331 482
12 15 349 687
5 42 245 749
41 28 886 981
38 30 229 688
45 4 961 991
21 2 464 701
50 37 920 979
38 37 422 639
5 22 672 906
44 50 12 726
46 11 470 737
30 1 722 943
35 49 802 827
13 13 192 828
43 13 166 221
18 17 902 993
21 49 399 508
13 27 428 662
12 3 289 593
41 43 259 282
18 3 367 849
1 37 319 999
1 19 153 209
39 20 129 833
30 33 658 743
11 7 22 602
40 23 565 618
49 14 950 951
23 30 394 433
16 40 188 400
24 48 896 897
24 1 685 740
35 32 75 805
29 14 902 974
25 32 532 678
46 45 707 728
48 19 272 896
43 4 337 577
39 27 717 734
8 13 454 843
43 7 443 482
5 28 71 641
46 4 64 870
7 50 468 820
16 32 768 869
22 7 285 893
23 27 248 552
44 22 614 925
43 29 144 227
48 45 295 312
50 24 662 761
11 44 594 726
12 28 749 831
37 6 114 534
30 15 36 325
21 15 63 181
23 38 795 980
25 25 25 111
49 49 309 605
48 4 944 951
9 18 391 554
19 26 348 620
46 26 262 574
41 35 767 800
45 37 640 762
13 40 869 940
17 47 683 871
32 34 119 367
24 45 376 934
37 6 641 928
46 31 81 152
2 20 533 546
3 28 181 844
4 19 108 640
44 9 234 960
1 30 395 692
13 44 576 862
1 3 760 998
36 35 64 768
34 14 713 852
2 41 539 769
43 21 777 951
37 29 633 781
10 42 816 887
2 32 728 879
5 48 370 484
41 14 264 649
1 25 327 981
6 49 67 600
10 26 778 867
35 7 69 658
27 46 977 992
3 21 593 927
36 18 120 776
31 28 387 881
2 17 115 874
10 30 687 945
29 46 565 977
19 29 922 975
18 49 970 980
7 18 110 725
15 50 531 960
43 27 582 983
34 42 17 960
41 15 473 652
28 47 860 875
36 10 298 792
23 10 18 806
32 42 33 155
9 28 182 344
39 37 342 487
10 6 574 582
23 28 974 989
31 9 931 983
16 21 915 933
41 6 274 807
32 32 555 721
24 9 701 735
12 35 15 520
35 30 760 895
21 21 770 890
37 26 923 966
49 21 870 943
37 45 306 336
13 22 425 836
19 22 51 715
23 49 438 763
38 37 732 920
3 38 766 794
45 6 727 862
19 34 758 974
21 32 745 927
16 2 54 960
2 10 621 734
49 5 170 979
16 38 18 322
32 39 734 981
10 15 914 916
37 25 656 738
46 39 623 775
4 1 100 214
42 42 619 674
45 1 853 912
27 1 616 666
20 44 578 602
36 6 212 402
26 14 472 609
22 12 878 901
13 8 53 907
24 12 261 432
29 16 175 930
48 7 534 671
20 34 851 874
20 8 34 577
23 4 156 163
4 49 535 996
11 7 302 484
6 19 265 961
29 4 954 972
36 42 240 808
24 32 1 868
19 40 562 761
14 38 276 516
49 7 67 156
23 7 188 880
29 31 142 162
45 29 829 834
48 37 555 587
45 32 863 895
17 35 871 962
47 14 456 656
41 26 425 671
5 33 555 817
50 200 50 1000
8 8 389 810
30 11 330 598
5 38 386 487
2 46 119 812
42 41 172 232
17 25 952 958
22 6 325 954
38 43 692 803
32 15 342 552
28 29 220 268
4 23 736 990
35 45 0 640
42 40 109 334
40 22 20 510
28 43 952 957
38 41 542 640
3 29 622 976
18 1 8 650
46 14 234 474
13 31 415 867
34 15 175 593
19 23 664 970
46 46 571 743
5 24 709 713
41 15 314 899
34 21 808 926
7 33 196 709
37 13 826 844
35 44 281 299
10 23 324 967
40 21 895 952
41 16 123 706
25 48 522 709
12 5 136 404
19 43 446 690
15 39 531 790
21 5 202 909
7 7 690 813
5 42 766 775
48 28 29 947
43 13 944 994
48 15 456 850
7 15 604 938
4 41 128 533
4 2 241 743
11 16 244 522
9 10 850 887
20 26 760 848
21 12 253 313
5 14 327 420
24 31 811 914
32 29 210 236
8 48 948 976
12 14 656 839
25 20 11 296
27 15 989 991
26 31 780 784
7 8 680 704
50 25 373 801
31 25 801 836
22 27 387 693
12 44 547 986
9 21 850 999
32 15 975 990
2 5 988 995
25 24 695 736
46 12 833 847
9 33 37 436
1 19 455 458
22 47 115 181
24 36 935 974
46 47 293 314
18 3 259 795
4 18 795 823
11 5 966 982
27 3 576 648
47 46 750 939
43 8 122 210
6 15 192 681
11 19 556 809
11 2 474 768
38 22 256 377
6 22 205 258
17 41 248 319
39 35 492 973
11 18 750 943
28 12 983 985
32 21 622 876
35 35 897 998
21 23 929 992
23 23 987 987
8 46 451 911
38 9 995 997
48 15 811 910
7 35 352 877
27 12 795 974
5 32 855 995
14 30 571 918
25 45 531 744
33 4 774 954
45 28 184 427
11 43 832 966
4 26 951 987
28 28 504 865
49 27 730 981
25 18 298 858
27 16 534 592
5 10 367 580
32 20 676 770
49 35 493 990
21 10 142 388
5 18 981 989
49 11 735 812
8 19 641 819
1 15 302 848
22 40 545 991
29 17 892 965
13 13 932 959
44 24 772 999
38 13 422 873
5 5 9 848
30 31 724 745
24 6 796 849
32 7 134 203
32 18 743 991
19 20 418 982
30 19 124 982
10 24 137 643
21 26 497 715
49 30 52 849
46 31 117 144
39 12 46 482
14 12 343 370
19 11 876 981
31 37 549 915
48 6 185 727
17 19 141 447
18 48 410 502
50 18 903 968
12 33 609 809
14 31 295 421
21 32 788 960
28 16 268 754
42 21 7 287
29 41 869 884
44 6 376 539
39 43 161 794
38 11 114 386
21 12 9 602
18 5 950 979
45 15 850 857
2 6 535 966
12 2 882 989
27 8 953 972
8 20 22 599
26 14 121 231
42 36 586 608
12 45 593 978
18 21 869 968
47 44 299 863
46 13 745 861
47 43 808 970
42 36 923 958
1 8 990 990
13 27 739 989
9 46 367 806
50 21 234 585
37 38 17 530
43 42 778 894
43 3 623 681
9 17 709 912
11 6 151 768
43 33 279 671
49 42 691 834
21 16 700 821
32 36 174 613
1 19 248 873
32 49 67 486
20 39 173 357
16 14 622 929
5 9 637 836
4 34 964 981
32 39 44 881
43 15 92 789
16 13 860 957
15 48 875 986
35 16 505 968
36 17 254 965
1 35 951 997
22 44 141 931
3 17 430 850
7 12 983 983
36 45 51 955
39 13 541 574
38 40 185 655
37 4 220 560
35 42 192 398
30 39 170 564
6 44 439 808
20 15 498 777
50 200 50 1000
38 14 605 639
29 43 816 864
37 31 101 841
12 16 788 982
3 37 444 580
42 41 336 787
27 13 395 530
5 38 5 741
8 48 428 514
42 18 964 983
38 17 388 682
37 35 3 768
34 5 863 927
24 37 645 692
34 42 40 41
50 43 836 977
12 25 490 589
29 42 525 956
26 11 612 874
6 23 469 796
29 40 448 558
28 16 762 888
25 13 211 655
34 34 913 915
19 44 115 732
8 34 781 856
39 25 62 108
11 11 302 783
15 46 318 578
30 17 761 776
43 13 561 778
37 27 285 671
30 44 580 723
25 24 353 920
1 49 470 737
24 7 391 630
48 9 391 422
19 4 909 935
30 33 810 863
12 7 256 822
23 13 696 703
3 18 746 843
45 13 305 832
37 32 858 964
45 26 53 918
11 30 198 444
28 27 442 704
22 48 154 977
41 37 188 320
10 9 501 607
10 42 493 639
35 26 761 956
5 38 873 934
33 5 747 986
1 25 72 580
31 1 585 780
37 22 372 862
40 19 465 540
27 48 61 241
28 18 528 796
14 41 872 905
48 7 563 836
22 48 993 999
16 10 679 796
11 7 639 956
11 22 674 742
34 11 212 573
25 9 632 911
47 9 839 903
48 40 167 407
40 22 402 735
25 11 818 931
14 48 233 690
35 8 342 916
28 38 318 422
11 28 8 248
46 47 205 596
35 42 582 961
2 37 790 975
10 9 363 878
35 47 834 941
45 28 477 490
41 29 346 351
12 45 701 786
3 46 959 992
23 37 190 288
9 19 23 216
5 23 854 865
2 44 445 747
46 20 595 737
5 11 208 940
21 6 261 510
14 28 120 656
28 33 940 967
33 37 585 726
30 30 214 885
24 9 69 195
31 29 61 568
48 20 529 944
13 30 366 865
36 36 260 260
28 28 430 801
6 22 508 509
42 11 432 875
47 1 699 960
14 2 531 926
20 19 355 848
9 30 194 334
20 19 575 914
11 42 353 714
32 28 468 568
7 4 235 496
44 24 100 461
25 24 17 479
1 4 277 705
38 32 23 403
47 8 6 951
41 20 796 831
12 1 566 711
23 6 252 804
25 42 897 994
29 35 62 390
46 46 478 823
5 34 580 720
34 41 920 998
18 10 913 935
42 40 278 714
12 30 163 567
26 1 462 975
4 32 523 867
7 21 218 298
37 9 620 838
50 27 827 995
2 12 454 456
39 14 81 837
15 20 337 473
26 10 99 563
47 9 478 525
41 30 232 488
2 38 243 571
48 4 658 861
27 44 662 800
16 27 263 700
2 9 459 562
33 23 37 148
27 27 737 740
44 6 562 976
6 1 458 506
5 48 96 669
36 38 31 640
4 35 395 428
40 40 644 694
5 33 713 750
30 17 469 595
28 3 313 640
48 40 476 543
39 16 445 785
5 5 428 429
15 9 993 998
27 36 544 841
40 16 869 949
45 31 446 841
18 33 828 932
20 27 245 302
17 40 565 954
32 17 77 213
4 4 845 924
21 25 934 994
44 42 938 993
40 6 393 941
41 33 802 855
2 17 724 833
1 10 346 899
22 20 909 969
21 21 521 813
2 13 295 409
28 27 235 565
34 32 959 999
42 20 812 840
12 44 394 678
39 9 240 646
36 13 772 986
10 29 552 892
24 23 881 913
26 8 455 697
1 42 796 872
34 39 770 798
49 1 507 526
32 30 340 641
30 50 7 510
7 27 793 871
42 17 777 822
43 10 959 995
33 48 253 335
28 43 816 831
29 25 577 845
2 49 513 903
14 14 883 951
22 12 453 938
34 46 440 732
41 200 50 1000
27 4 95 844
11 20 814 819
12 16 764 943
34 48 454 991
27 30 359 685
39 41 623 843
9 41 942 951
36 21 33 170
1 18 562 994
31 21 672 724
23 18 740 824
20 17 751 843
27 17 907 911
10 16 14 772
37 12 582 700
14 28 868 957
27 23 725 772
15 27 659 913
1 31 5 572
13 6 429 784
16 3 683 785
24 8 631 661
2 38 461 521
19 8 660 724
32 2 882 962
35 41 476 535
26 30 836 944
8 22 285 485
19 7 310 318
32 46 998 998
35 2 752 919
28 6 174 743
31 41 345 894
6 40 226 587
26 31 16 845
8 8 955 994
28 48 272 772
14 49 894 905
14 5 759 926
19 6 493 531
5 43 24 984
11 43 955 985
40 8 129 985
16 43 372 612
22 18 586 755
38 41 885 936
35 26 607 916
2 45 784 995
7 25 803 960
27 23 812 976
14 46 275 653
8 34 463 785
32 22 512 933
40 19 727 872
35 39 622 734
11 49 557 933
39 37 224 514
39 44 312 632
31 31 723 814
8 49 591 619
21 34 824 915
10 13 128 841
22 21 867 908
31 8 906 978
9 30 961 984
29 43 220 927
1 31 974 999
15 39 226 940
3 23 130 420
21 46 371 409
6 20 369 569
6 17 242 621
3 39 608 731
39 34 547 952
25 12 765 991
37 50 362 492
31 3 740 869
19 37 304 917
18 16 517 528
28 5 15 203
1 5 255 803
30 10 155 465
11 45 491 592
14 34 166 318
19 40 584 872
22 11 194 497
36 39 132 871
34 33 919 951
37 27 377 819
4 15 479 934
16 41 549 829
5 37 370 448
26 48 686 817
31 42 942 961
35 28 719 881
16 32 92 812
35 50 514 615
15 18 863 969
29 42 119 165
33 42 901 905
24 26 686 942
38 6 158 651
25 48 393 781
16 8 801 807
6 23 256 728
37 2 9 822
4 27 860 863
25 40 244 937
2 43 906 958
27 19 609 947
8 7 974 989
25 33 113 508
10 2 30 419
36 9 34 523
19 28 37 55
13 4 52 898
35 22 484 616
27 39 519 942
15 15 772 828
3 10 60 907
36 24 184 429
34 45 649 956
38 13 575 834
33 41 482 967
11 2 36 919
36 42 242 923
11 4 531 977
32 19 787 867
37 21 875 894
3 46 943 948
40 26 532 540
4 2 788 891
39 11 392 946
1 18 790 887
39 42 63 550
31 38 192 831
22 3 255 458
31 3 287 577
34 47 509 783
18 10 628 838
1 22 863 864
34 46 732 919
6 45 49 396
6 50 548 784
9 43 463 536
9 44 846 986
2 5 474 758
18 2 634 944
19 12 572 968
36 31 948 985
10 50 518 636
22 16 626 693
35 15 912 995
23 34 209 784
2 18 519 530
9 43 699 769
29 2 328 934
35 25 754 910
2 21 507 603
31 37 791 808
33 46 377 622
25 22 627 989
2 24 41 68
7 46 520 701
32 8 558 932
20 4 889 960
25 25 386 455
16 39 596 984
5 19 389 543
9 6 371 430
38 3 848 944
6 19 863 956
6 16 781 886
11 36 855 963
25 39 368 688
40 41 363 605
20 29 426 562
36 7 694 716
20 34 691 845
10 17 81 344
19 23 142 172
11 5 140 582
2 23 695 968
8 42 249 544
24 11 404 792
35 3 917 994
16 32 724 798
31 18 362 676
5 48 488 994
3 19 783 895
13 33 989 993
8 1 303 939
9 1 970 979
5 14 121 255
34 43 385 646
37 10 214 377
18 12 502 662
36 29 817 962
39 40 294 923
10 27 11 309