12 15 8 9 4 3 2 3 4 3 4 3 2
 1000 1000 
 4 54 128 0 48 0 0 60 0
 5 54 128 60 0 240 0 0 286 0 48
 3 0 508 0 286 240 0
 4 946 82 844 0 1000 0 1000 104
 5 946 82 1000 104 1000 228 648 0 844 0
 3 1000 790 1000 1000 698 1000
 3 648 0 1000 228 1000 790
 3 648 0 1000 790 698 1000
 4 522 368 522 0 648 0 668 400
 5 522 368 668 400 678 600 240 0 522 0
 3 294 1000 0 1000 0 822
 3 240 178 120 254 240 0
 4 240 178 240 0 678 600 120 254
 4 294 568 0 616 0 508 120 254
 7 294 568 120 254 678 600 698 1000 294 1000 0 822 0 616
 3 0 608 0 0 658 0
 3 658 0 1000 0 1000 598
 3 1000 598 1000 1000 674 1000
 4 378 924 192 1000 0 1000 0 728
 5 378 924 0 728 0 608 674 1000 192 1000
 3 1000 598 674 1000 0 608
 4 658 132 658 0 1000 598 200 606
 4 658 132 200 606 0 608 658 0
 3 1000 370 1000 1000 540 1000
 4 122 166 0 194 0 0 462 0
 5 122 166 462 0 550 0 0 404 0 194
 3 240 1000 0 1000 0 404
 4 294 698 724 748 540 1000 240 1000
 5 294 698 240 1000 120 702 816 622 724 748
 4 552 246 908 496 816 622 642 642
 8 552 246 642 642 468 662 0 404 550 0 1000 0 1000 370 908 496
 3 468 662 120 702 0 404
 4 918 744 1000 966 1000 1000 890 1000
 5 918 744 890 1000 790 1000 1000 506 1000 966
 7 166 272 130 1000 0 1000 0 0 1000 0 1000 506 790 1000
 3 166 272 790 1000 130 1000
 3 674 0 1000 0 1000 300
 6 676 930 1000 654 1000 1000 0 1000 0 0 674 0
 4 676 930 674 0 1000 300 1000 654
 3 614 1000 0 1000 0 416
 5 0 416 0 0 1000 0 1000 1000 614 1000
 3 584 558 0 530 0 278
 7 584 558 0 278 248 0 1000 0 1000 1000 0 1000 0 530
 3 0 278 0 0 248 0
 4 760 146 1000 188 1000 556 404 0
 4 760 146 404 0 1000 0 1000 188
 6 404 866 1000 856 1000 1000 0 1000 0 0 270 0
 5 404 866 270 0 404 0 1000 556 1000 856
 3 566 0 1000 0 1000 298
 4 446 318 134 1000 0 1000 0 194
 7 446 318 0 194 0 0 566 0 1000 298 1000 1000 134 1000
 4 898 178 732 0 1000 0 1000 158
 5 898 178 1000 158 1000 288 622 0 732 0
 4 496 504 0 364 0 0 392 0
 7 496 504 392 0 622 0 1000 288 1000 1000 0 1000 0 364
 3 1000 548 1000 1000 614 1000
 4 804 282 308 1000 0 1000 0 522
 7 804 282 0 522 0 0 1000 0 1000 548 614 1000 308 1000
 3 1000 394 1000 1000 654 1000
 5 654 1000 0 1000 0 0 1000 0 1000 394