P14962 [HackerEarth] Barbarik was the grandson of Bhima and the son of Ghatotkacha. Barbarik was supposed to be a brave warrior having learnt the art of warfare from his mother. Lord Shiva pleased with Barba
普及
题目描述

Barbarik was the grandson of Bhima and the son of Ghatotkacha. Barbarik was supposed to be a brave warrior having learnt the art of warfare from his mother. Lord Shiva pleased with Barbarik's talent as a warrior granted him special arrows. Assuming the Battlefield as a 2D Grid, these arrows can kill all men standing in a row or in a column in 1 second . Before the war started, Lord Krishna asked everyone how long would it take for them to finish the war alone. Bhisma replied it would take 20 days. Dronacharya said it would take 25 days. Karna said it would take 24 days whereas Arjuna said it would take him 28 days.Krishna having heard of Barbarik and wanting to examine Barbarik's strength disguised himself as a Brahmin came in front of Barbarik. Krishna asked him the same question about how many days would it take to finish the war if he were to fight it alone. Barbarik seeks your help to answer this question. Assuming battlefield as a 2D grid of cells. Each cell may or may not contain a soldier. You are given the list of cells that contain warriors of opposite side. You have to tell the minimum number of seconds that will be required by Barbarik to finish the war (killing all the soldiers).

Input
The first line contains T the number of test cases. The first line of each test case contains N the number of cells where enemies are present. The following N lines contain two integers X and ** Y** each describing the index of the position of soldiers of opposite side.
Output
For each case print the minimum number of seconds that Barbarik need to finish the war alone. (kill all soldiers of opposite side )
Constraints
1 ≤T ≤ 10
1 ≤ N ≤ 1000
0 ≤X, Y ≤ 1000000000

SAMPLE INPUT
2
5
0 0
1 0
5 0
0 2
0 4
4
1 0
0 0
0 1
1 1

SAMPLE OUTPUT
2
2

输入格式

见题面

输出格式

见题面

样例输入
5 20 56 55 38 21 77 64 99 35 42 89 94 27 56 49 78 85 94 79 63 73 86 63 69 36 11 11 80 30 72 6 33 72 88 90 67 64 7 57 67 74 50 8 63 79 69 39 52 28 31 54 83 71 21 48 89 2 0 7 32 89 89 24 72 65 23 38 37 13 97 65 16 76 9 13 11 61 22 16 21 1 48 94 64 100 13 99 21 8 74 84 94 5 91 11 2 54 26 13 57 64 76 10 19 62 13 18 87 26 30 71 64 61 55 81 57 88 22 36 39 25 82 7 78 42 90 12 52 61 84 5 51 41 18 74 67 78 42 34 23 87 18 80 96 63 29 15 19 89 39 57 77 87 75 84 55 92 92 19 81 59 18 41 20 51 59 72 36 20 46 94 0 29 70 16 65 44 85 30 94 37 9 10 26 36 100 47 55 92 98 82 22 78 77 21 33 74 55 4 16 14 27 89 33 61 53 84 2 64 54 77 37 4 15 4 66 84 20 92 29 48 4 4 54 64 97 87 82 44 27 88 66 35 98 50 44 46 34 39 6 50 49 70 85 41 86 58 56 45 71 91 41 73 6 83 39 88 76 14 91 89 100 44 24 44 22 14 26 28 72 32 62 44 85 70 21 66 97 7 84 19 10 92 97 73 82 6 44 88 44 30 28 50 76 9 59 41 57 46 87 48 22 17 100 302 707 203 283 436 653 767 105 318 650 128 242 506 491 924 86 646 622 243 161 205 194 935 268 632 711 641 482 125 193 575 369 397 476 571 827 295 618 164 269 581 541 640 927 773 342 820 780 528 196 655 334 16 797 690 36 571 787 373 16 415 872 864 894 276 373 810 137 554 512 939 909 620 677 237 647 682 338 723 728 501 384 719 213 13 466 772 229 918 909 95 405 802 586 105 644 822 733 478 810 43 911 322 579 754 153 303 315 98 971 230 227 561 870 659 537 828 149 106 4 168 8 894 315 670 605 181 581 881 58 823 581 797 465 524 806 816 287 360 442 420 304 232 509 477 393 745 983 928 222 767 952 829 801 557 357 675 685 866 146 814 411 258 943 389 361 221 425 777 313 239 216 166 509 576 817 541 487 633 743 175 407 378 121 532 652 234 552 768 260 332 530 521 189 689 968 115 684 451 415 100 954 388 638 625 529 529 172 576 152 198 277 476 735 307 141 71 725 156 779 484 594 240 178 663 596 96 348 461 563 536 494 7 66 180 426 276 35 153 849 913 350 359 297 597 781 827 932 820 519 13 39 917 66 787 219 42 556 713 974 621 705 171 393 816 154 952 593 700 434 673 410 665 676 490 715 970 737 379 825 826 663 219 617 714 822 104 605 849 195 470 102 295 60 456 532 100 347 297 378 608 591 266 106 316 268 765 674 691 697 420 83 760 519 512 8 251 107 776 743 655 84 986 73 969 18 990 571 961 846 895 466 104 986 459 496 671 261 531 692 338 194 269 27 352 136 88 323 263 91 296 536 914 733 938 232 867 81 64 828 792 786 872 42 137 725 697 129 953 560 381 501 918 2 698 703 833 461 617 778 2 540 887 558 945 823 664 522 687 631 235 826 851 800 956 446 119 29 384 73 207
样例输出
50 98 198 290 379