TEST DATA FOR `fence'

Input for test 1

6
5 5
2 3
3 2
1 5
5 1
1 1

Output for test 1

5

Input for test 2

8
661 233
174 881
284 955
666 512
59 767
863 393
27 715
76 312

Output for test 2

7

Input for test 3

10
499 540
544 500
540 501
503 459
459 504
539 504
503 460
464 498
501 542
463 502

Output for test 3

7

Input for test 4

12
644 397
582 648
741 138
547 125
90 701
121 538
732 474
469 443
159 776
169 577
661 5
452 708

Output for test 4

9

Input for test 5

15
728 965
285 32
723 965
839 940
611 977
62 163
618 980
724 968
949 806
283 38
617 975
723 964
172 60
611 974
174 57

Output for test 5

8

Input for test 6

20
323 100
410 31
486 3
408 30
486 1
165 378
814 324
648 76
86 584
649 76
487 1000
491 1000
163 380
328 103
813 322
649 77
80 582
568 18
404 26
326 104

Output for test 6

12

Input for test 7

40
51 697
441 583
796 966
454 481
674 279
246 526
701 244
678 280
792 946
1000 893
478 627
305 586
258 720
517 483
556 876
768 606
924 560
188 71
878 994
551 903
272 797
428 324
40 458
604 183
403 955
427 880
581 731
818 190
451 334
24 6
561 791
964 836
703 151
906 580
496 457
605 261
443 996
718 398
178 473
704 605

Output for test 7

12

Input for test 8

55
199 767
205 764
857 683
730 170
728 168
201 765
361 875
202 762
357 874
731 170
203 234
548 900
727 168
109 404
115 407
728 172
549 900
358 126
859 689
549 101
112 595
852 683
903 503
362 125
548 899
356 872
729 173
903 502
199 236
900 501
858 689
113 595
899 499
360 877
851 686
110 599
112 408
855 315
360 878
114 594
547 899
357 128
859 685
361 123
356 127
114 599
725 171
551 102
113 594
901 499
204 763
855 687
110 403
111 598
200 770

Output for test 8

22

Input for test 9

65
577 19
520 998
314 117
5 832
421 22
1 829
105 521
158 392
208 282
3 831
418 20
213 284
419 24
831 373
625 55
780 261
419 26
518 2
574 16
782 263
420 27
835 368
779 261
207 280
525 998
1000 830
835 367
677 105
415 24
574 19
416 21
313 118
524 1000
731 176
3 829
627 52
779 263
784 262
367 59
262 190
365 61
209 283
575 18
523 1
210 280
509 918
783 266
1 831
2 832
837 368
2 834
156 391
160 391
207 285
158 393
625 53
833 373
208 285
524 999
628 54
831 372
521 999
263 192
261 192
469 5

Output for test 9

27

Input for test 10

80
406 394
857 531
275 462
228 466
276 454
629 576
810 535
542 742
629 580
451 296
630 580
226 465
90 478
454 294
633 575
409 395
136 473
674 553
268 461
276 455
634 575
721 545
496 3
49 477
271 454
270 462
92 478
407 395
677 558
91 475
681 561
628 577
317 448
859 528
677 559
814 536
450 294
450 295
51 483
93 474
811 536
48 475
183 471
89 479
675 559
93 476
182 471
405 398
856 533
409 398
3 480
814 537
854 527
407 397
630 574
815 534
857 532
815 530
136 472
768 539
586 616
809 533
496 2
227 464
544 743
589 615
360 432
498 3
543 742
589 618
861 532
586 615
543 744
497 2
626 725
4 256
998 686
416 629
942 160
782 12

Output for test 10

16

Input for test 11

100
498 478
485 486
514 519
486 487
491 518
483 494
492 484
503 485
497 482
487 485
479 507
501 480
489 479
480 494
486 512
483 510
491 520
482 492
516 486
481 505
495 521
502 477
513 517
481 489
494 518
514 488
540 589
387 791
434 125
979 220
909 831
622 800
869 415
219 125
50 971
973 205
84 924
943 57
30 775
952 921
363 88
432 750
878 866
226 856
437 134
38 410
285 259
824 855
383 225
826 707
429 261
630 723
669 915
80 50
689 32
970 52
471 753
153 348
618 378
556 406
815 796
851 990
2 585
214 179
292 995
439 921
69 459
835 149
508 876
532 829
927 354
582 79
53 551
456 608
957 318
553 123
465 755
113 467
340 678
645 631
672 436
903 741
894 90
241 402
965 124
582 891
477 163
321 529
489 22
93 41
144 910
795 256
376 134
286 372
116 957
807 19
49 701
108 641
116 35
314 944

Output for test 11

18

Input for test 12

130
284 241
431 48
114 130
542 17
916 14
119 850
635 116
99 90
695 469
30 226
633 512
432 46
632 353
690 988
84 990
545 56
165 287
562 981
563 984
401 72
696 1000
160 135
157 915
381 107
15 190
161 80
956 333
696 989
252 389
670 971
41 398
236 219
102 279
951 338
544 451
692 397
214 382
629 117
972 263
435 48
30 118
838 970
944 116
669 496
119 977
693 997
634 112
290 245
813 72
435 196
594 113
795 57
239 84
182 362
854 3
249 386
918 12
101 89
633 117
14 859
15 193
287 376
100 352
948 79
166 80
841 150
973 263
131 97
284 245
286 243
811 24
880 156
473 41
265 113
634 510
185 358
545 16
118 982
506 189
692 987
780 84
954 75
164 289
113 319
942 112
75 253
839 43
98 94
853 5
404 178
402 174
382 145
86 996
164 326
709 950
286 240
49 838
214 384
98 89
17 862
792 56
507 59
314 344
917 11
795 60
404 179
46 838
668 970
182 363
102 92
969 259
202 70
117 171
19 861
668 500
205 75
115 174
29 118
631 514
163 288
973 261
137 106
155 915
741 78
532 162
202 230
593 107
17 863
566 379
540 126

Output for test 12

23

Input for test 13

170
358 493
418 541
365 469
510 644
539 647
471 649
402 441
543 635
452 677
345 563
308 538
322 560
320 541
401 526
460 605
309 477
306 458
493 644
368 530
544 647
566 608
317 519
348 534
516 673
400 548
453 603
466 620
493 688
478 679
415 500
507 604
554 669
327 539
487 361
481 699
512 616
509 372
495 590
512 621
531 689
535 654
539 625
535 692
568 608
507 661
319 534
400 484
311 531
568 610
419 563
465 613
435 641
561 668
509 650
510 656
484 360
513 570
380 482
546 600
386 461
500 685
452 613
503 578
398 501
441 661
390 441
453 592
449 607
380 478
563 697
567 663
480 692
346 532
467 672
363 524
349 504
428 469
377 499
398 453
334 466
491 371
552 596
307 495
492 637
438 632
634 503
448 641
426 458
304 484
528 576
354 438
487 378
319 561
436 576
321 477
474 697
462 689
320 551
442 694
312 442
374 558
412 448
246 156
128 542
619 495
397 410
997 77
918 539
697 740
959 51
782 561
192 865
115 194
757 787
795 497
4 804
934 974
650 683
759 652
858 524
760 401
780 207
500 519
657 517
104 980
261 107
135 547
229 815
783 987
146 209
166 3
85 925
403 824
231 182
30 730
52 752
338 708
621 793
39 881
900 174
310 7
994 964
410 139
173 927
203 247
784 433
780 166
269 204
890 889
996 280
122 247
805 900
578 114
259 76
39 967
893 586
171 448
832 307
880 611
472 394
793 740
597 682
981 945
961 454
191 766
705 769
196 788
566 234
754 659
596 319

Output for test 13

22

Input for test 14

200
1000 833
88 565
698 131
87 564
491 2
62 649
467 6
1000 831
526 3
580 21
321 109
60 651
28 736
870 460
324 106
89 567
324 109
522 1000
207 291
757 216
725 167
206 291
293 146
730 169
553 8
549 6
872 457
555 8
320 112
349 77
264 186
119 488
497 998
812 327
465 5
871 460
641 64
755 217
491 4
553 10
874 458
844 391
289 149
292 146
812 329
438 12
207 294
668 93
494 4
842 389
668 94
34 739
262 185
264 193
729 170
3 831
318 110
34 740
2 830
294 147
294 148
815 328
549 7
671 96
292 147
497 997
496 5
1 828
28 737
267 190
498 2
63 646
177 351
723 174
554 12
263 192
260 193
61 647
435 16
4 830
325 107
4 829
262 189
175 353
204 292
318 111
784 270
999 828
897 727
729 169
697 129
499 997
727 175
582 20
641 65
787 269
178 351
726 174
57 650
584 22
496 999
245 566
435 13
786 267
89 565
439 16
639 65
409 28
239 328
662 940
951 44
521 911
879 294
441 664
468 282
979 290
545 30
928 822
236 497
102 624
178 418
576 379
244 166
706 148
339 367
87 642
763 959
552 993
252 344
656 71
625 987
360 521
368 639
342 603
226 664
394 456
319 452
603 10
170 42
3 932
925 252
249 932
322 873
270 34
394 638
240 159
530 818
822 741
323 568
548 993
19 151
354 188
192 356
472 543
261 396
794 509
679 468
382 949
853 127
938 524
213 529
698 208
187 20
775 734
365 793
236 718
332 779
74 803
322 686
550 467
195 229
286 928
406 466
14 618
994 47
254 602
63 28
687 779
53 922
306 726
607 856
545 153
80 964
320 485
781 333
455 126
379 870
169 985
471 584
12 509
783 858
391 188
779 696
913 738
903 457
890 690
639 970
5 958
806 137
481 431

Output for test 14

45

Input for test 15

225
195 757
282 832
233 204
880 619
233 201
281 834
826 728
634 876
579 891
230 796
518 901
831 271
519 99
285 832
105 533
576 896
689 148
824 728
110 406
125 348
742 180
397 887
396 890
856 678
894 559
282 165
189 757
745 182
581 893
830 730
126 352
236 799
856 676
576 108
285 163
130 649
339 867
575 107
339 864
517 901
397 116
638 878
517 99
694 147
104 528
236 803
787 223
393 113
110 411
739 183
396 882
639 876
513 102
861 679
337 138
195 755
109 412
881 378
695 852
898 438
636 879
338 138
125 351
886 384
579 894
788 223
155 704
880 383
104 469
157 706
575 108
633 875
391 885
858 676
338 135
234 203
894 437
581 894
159 705
281 840
882 621
693 854
102 471
861 681
126 354
859 681
113 590
860 675
580 105
574 110
457 899
827 270
690 147
130 651
885 378
105 528
743 820
828 267
191 753
453 106
102 469
337 865
824 731
230 803
518 100
744 182
106 531
741 178
827 268
394 882
514 899
336 868
884 619
237 204
454 106
113 411
157 296
519 103
691 152
132 355
898 565
895 440
879 379
830 729
689 855
340 135
899 564
742 181
335 137
100 532
829 733
340 134
883 381
156 707
902 499
455 102
825 273
893 562
237 798
193 752
111 591
158 297
106 534
283 165
101 468
159 703
108 409
158 703
580 111
896 438
900 502
127 347
899 501
109 408
133 348
901 502
743 818
609 170
966 604
116 110
298 533
683 715
276 354
289 149
352 403
533 481
196 62
221 512
872 4
983 754
803 957
478 235
366 593
696 664
730 753
84 18
901 787
773 434
620 613
460 815
26 680
678 897
683 660
2 837
616 271
247 445
858 612
283 709
267 718
78 520
305 475
814 764
642 192
88 829
331 442
665 298
64 263
226 780
826 205
294 460
913 560
529 990
79 384
192 383
498 852
548 644
522 988
429 488
765 328
23 942
532 316
227 929
785 658
685 242
77 584
885 599
450 351
196 599
842 959
900 156
531 652
951 758
767 595
821 451
34 636

Output for test 15

53

Input for test 16

230
61 178
910 892
254 42
128 76
919 877
312 34
329 30
86 117
911 894
331 30
220 46
924 871
88 118
772 958
709 968
60 180
224 44
74 141
619 978
814 945
501 981
604 974
813 945
280 37
728 969
923 877
606 976
686 969
620 976
251 40
327 33
70 142
533 983
608 974
84 113
254 38
593 981
195 55
59 177
920 871
323 29
994 499
713 970
941 848
819 948
725 963
860 927
135 74
148 68
966 708
129 75
729 967
196 57
166 61
711 967
280 35
862 933
265 35
165 67
787 955
999 503
727 962
101 101
893 908
1000 505
831 942
860 930
75 141
696 973
590 975
59 179
701 965
11 500
1 504
832 944
907 892
609 977
859 927
532 982
965 706
148 70
60 181
999 499
903 891
918 872
195 49
53 177
327 32
814 944
940 845
909 894
221 48
910 891
889 910
680 972
311 32
936 848
1000 498
786 955
58 175
995 501
923 874
996 506
785 957
895 908
941 842
996 498
91 117
981 502
952 797
952 799
965 705
969 707
537 36
111 3
507 524
284 438
530 130
844 370
202 829
191 740
332 794
239 523
756 536
225 106
309 962
255 267
319 792
654 105
89 116
459 596
639 743
224 228
538 425
56 80
516 387
225 754
909 980
290 485
446 692
216 116
835 869
573 923
336 31
493 348
124 184
461 639
745 183
16 34
668 453
335 113
496 550
229 330
770 801
252 105
183 122
430 308
7 504
304 131
39 764
121 961
801 865
250 163
972 584
275 467
796 606
7 400
710 542
521 139
201 895
398 716
689 789
479 810
749 631
26 244
799 276
406 770
859 681
589 696
887 736
301 246
135 363
787 7
902 265
193 651
980 234
791 811
43 540
441 68
783 591
695 541
713 554
573 301
601 459
36 901
704 523
615 842
732 373
785 712
606 575
114 314
67 249
667 361
269 267
171 304
519 227
826 134
68 707
601 896
488 684
268 624
747 873
199 620
872 664
286 938
764 778
433 854
339 228
475 156
974 742
780 73
966 978
993 329
127 905
246 72
6 589
137 518
551 475
97 867
765 572

Output for test 16

44

Input for test 17

235
651 529
406 367
555 421
418 411
329 593
513 644
588 479
557 608
418 676
630 378
379 563
617 555
647 413
436 647
461 648
540 391
473 627
452 675
475 698
486 391
373 617
399 386
570 459
581 527
369 629
474 360
463 575
465 628
535 593
561 474
654 455
470 380
605 573
668 486
645 587
514 671
379 400
683 342
349 588
459 639
618 428
443 658
661 342
615 557
598 368
463 389
505 600
461 392
579 410
523 659
471 311
488 647
385 603
464 442
613 376
454 554
473 392
601 534
381 413
645 371
523 661
654 341
633 481
627 621
399 547
535 629
324 618
668 503
450 552
554 551
543 559
496 336
546 497
353 622
667 335
543 328
572 569
530 668
683 384
331 630
332 655
610 388
641 358
579 446
641 371
444 407
498 602
384 375
381 368
623 548
459 621
446 356
550 652
566 558
400 670
510 313
363 622
514 642
623 628
642 432
642 335
555 370
462 657
545 308
658 373
635 668
398 541
610 396
627 457
503 660
468 676
330 654
336 636
526 332
647 500
493 663
626 405
597 502
665 388
572 401
625 467
576 581
348 550
395 568
529 685
477 655
457 333
444 500
393 587
385 653
411 571
648 337
393 399
653 508
377 566
609 667
329 570
344 513
649 369
392 608
545 601
650 462
505 336
453 347
652 541
448 354
547 355
688 82
933 488
247 108
389 654
116 340
633 826
310 145
180 65
85 219
58 745
750 592
170 606
204 12
747 686
950 983
740 583
160 868
364 352
62 544
866 820
617 111
933 402
822 102
7 25
466 753
87 801
349 246
21 249
66 384
601 127
624 393
985 490
564 346
809 468
921 939
43 67
801 481
219 501
750 144
622 605
69 246
87 264
751 269
736 728
188 657
19 193
542 830
695 619
420 444
981 51
618 419
315 369
39 110
927 775
783 207
131 870
616 707
368 889
730 34
609 768
495 887
894 684
353 28
337 277
373 787
44 856
8 606
100 623
664 431
940 286
742 660
21 484
871 725
792 66
973 128
694 3
896 357
433 188
847 520
726 26
773 948
60 894
131 984
912 824
338 159
533 123
346 527
648 544

Output for test 17

27

Input for test 18

240
64 639
273 177
755 214
182 343
483 5
209 282
389 39
707 145
4 831
318 113
64 640
483 999
497 1
585 26
601 34
420 18
800 296
33 738
241 223
600 33
558 10
49 692
797 295
78 600
571 17
16 778
842 385
165 368
395 36
800 295
246 228
239 223
693 122
793 290
589 26
244 224
590 27
735 187
438 13
244 222
748 214
93 558
363 65
44 684
328 94
421 24
182 336
48 687
658 89
711 142
46 684
434 10
574 19
529 3
451 7
999 833
169 375
334 93
631 61
167 375
238 226
465 6
485 3
336 99
30 730
381 54
646 74
63 639
425 22
420 17
842 391
210 279
123 476
810 323
5 829
748 207
845 389
810 322
375 49
179 339
306 136
303 136
439 11
617 45
66 640
425 20
574 14
739 188
32 738
433 14
708 140
121 479
711 141
139 442
34 736
246 222
999 829
793 291
785 267
238 225
179 336
751 208
21 781
511 1
389 44
782 261
484 999
813 324
781 267
274 175
124 476
513 1000
772 472
524 12
338 965
239 272
243 235
340 858
370 525
259 751
399 966
601 162
445 973
519 76
291 922
809 439
662 848
651 243
757 526
606 447
718 84
431 409
941 800
517 854
845 313
826 363
285 197
906 298
44 908
540 152
433 498
693 20
710 475
626 713
554 879
396 70
732 240
382 910
955 122
377 591
670 283
888 713
217 327
276 166
953 321
147 965
16 773
677 569
664 372
996 970
493 372
654 447
227 548
226 795
874 853
313 826
525 849
839 672
165 207
796 842
775 798
618 765
884 281
488 879
603 332
846 256
961 425
803 186
219 28
390 883
205 915
84 396
586 248
602 733
441 728
492 766
691 331
644 293
663 246
806 508
502 766
932 656
303 503
684 693
385 240
607 468
635 544
68 236
276 508
316 157
566 159
922 608
900 152
515 705
11 368
471 943
24 773
797 59
298 775
1 285
872 297
927 187
454 844
346 727
451 835
338 511
407 348
878 229
642 253
1 438
663 170
971 961
944 971
390 468
262 668
655 715
512 1000
794 962
186 141
664 523
3 70
650 864
485 650
593 408
80 334
875 341
354 529
408 865
880 553
45 841

Output for test 18

46

Input for test 19

245
113 396
110 395
891 418
671 863
391 886
706 847
425 894
165 713
670 863
902 460
770 208
893 417
163 712
217 778
218 780
127 640
593 110
551 107
391 884
882 619
187 252
388 117
879 624
162 712
634 126
184 752
467 900
771 793
672 140
513 99
592 888
773 208
432 890
242 195
312 150
349 873
186 251
352 128
387 114
315 851
704 844
847 699
632 879
705 846
473 99
897 538
390 884
705 843
552 896
896 460
890 582
125 639
275 171
315 144
894 422
555 104
184 750
117 401
472 105
311 855
387 886
870 342
553 105
889 580
350 868
141 678
849 303
823 268
847 303
160 713
850 697
143 678
896 586
427 108
352 129
895 540
309 143
590 887
112 603
884 381
890 586
864 342
427 894
594 887
595 891
830 270
552 895
828 268
142 675
139 681
591 113
466 104
710 846
141 676
110 403
162 287
554 107
592 889
312 855
129 639
866 662
589 110
510 100
889 416
279 167
553 106
213 782
433 893
774 203
469 103
466 102
895 539
555 899
163 715
801 765
277 835
882 625
893 421
165 284
864 340
187 747
851 695
891 422
591 111
868 343
388 118
275 833
139 676
313 151
513 101
218 778
276 171
147 681
823 273
278 167
898 540
900 542
594 112
512 102
775 210
883 625
316 857
113 398
899 545
103 481
112 401
881 623
279 834
846 696
102 478
161 287
827 732
892 582
103 480
828 731
210 776
101 478
117 395
274 831
309 151
114 397
116 402
140 682
243 807
742 821
435 947
495 659
616 826
247 969
736 190
19 739
568 229
791 57
38 356
877 880
419 101
554 474
532 48
133 147
873 731
272 486
699 449
604 618
677 768
325 819
824 362
175 52
773 12
597 607
638 480
654 122
978 878
204 445
838 475
282 888
653 830
122 828
543 296
880 136
168 448
556 157
278 904
348 628
659 629
866 372
236 518
345 447
356 576
881 108
903 807
668 532
710 458
364 410
307 255
674 895
124 578
603 469
25 959
396 959
73 624
782 242
858 843
51 221
252 839
595 642
147 372
744 750
840 120
708 587
78 269
562 821
383 634
961 577
420 600
438 337
589 264
635 192
837 826
311 544
164 325
913 547
959 709
503 271
88 408
431 88

Output for test 19

57

Input for test 20

250
289 517
405 277
396 551
545 444
440 380
297 578
590 306
483 357
488 404
432 360
424 308
495 322
484 477
406 402
493 327
464 543
490 557
459 579
353 497
480 418
390 465
538 274
409 441
352 478
477 303
371 480
346 449
526 296
296 465
409 382
522 331
437 355
541 540
528 524
511 373
334 505
527 440
492 367
521 371
559 403
546 445
555 268
522 308
513 427
394 454
410 377
530 322
527 421
493 402
445 265
536 257
445 287
308 495
291 555
472 416
548 340
384 500
583 337
514 320
480 406
340 525
428 330
481 499
319 557
438 356
532 344
411 404
432 362
596 264
587 419
353 483
462 377
582 346
511 288
311 495
594 273
466 276
582 313
308 310
525 403
416 263
386 499
482 439
413 276
554 369
566 303
557 416
530 316
585 386
501 588
554 384
585 279
333 528
537 470
407 559
486 326
407 510
365 454
360 513
367 467
538 484
411 474
363 474
375 560
366 547
550 389
558 433
556 371
490 527
310 431
320 487
704 562
209 658
505 650
793 451
142 521
135 312
621 143
422 840
959 985
178 996
952 660
988 965
955 817
581 658
378 208
274 938
587 9
229 205
923 722
385 698
551 807
537 862
209 95
725 196
365 991
198 315
32 414
93 618
175 697
394 900
105 131
937 485
221 79
550 429
525 627
977 935
658 341
926 698
889 456
435 14
710 874
860 167
171 502
533 180
842 810
285 241
740 525
134 600
401 345
152 643
399 147
740 121
692 265
767 251
61 271
883 697
221 559
500 110
87 986
709 839
595 834
468 993
980 207
465 23
824 535
237 590
786 630
197 198
246 114
758 818
673 609
927 111
594 988
813 543
461 633
888 792
32 152
925 635
935 170
987 420
252 831
873 65
725 333
476 239
668 642
633 427
61 644
726 809
687 712
976 462
936 580
292 808
980 967
961 238
256 4
797 888
783 858
444 843
854 169
3 540
232 935
396 165
138 39
406 815
134 810
735 94
399 990
877 231
405 672
192 428
149 423
334 109
895 471
499 219
956 905
993 870
292 728
963 691
69 764
994 641
321 771
898 513
935 912
777 620
373 23
91 871
241 46
495 820
510 619
925 746
268 270
739 589
41 636
101 591
34 387
854 162
7 226
449 777
494 927

Output for test 20

25