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