P14013 [HackerEarth] "Intelligence is a very result of hard work, behind every drop of intelligence there is a ocean of hard work" - Unknown
普及
题目描述

"Intelligence is a very result of hard work, behind every drop of intelligence there is a ocean of hard work" - Unknown

So our guy Ankur likes a girl G very much. But as we all know G likes only intelligent guys.
So if Ankur has to impress her then he has to show his intelligence. But G too is an intelligent girl, so he came up with a task for Ankur.
The task is -
Ankur has to collect flowers for her and put them into baskets, but flowers are scattered all around,
each flower has a position say (x,y). Each basket can hold only two flowers, but putting flowers into basket has a special cost.
If two flowers at positions (x1,y1) and (x2,y2) are being put into a basket then cost of putting them will be
the euclidean distance between them ( sqrt(square(x2-x1) + square((y2-y1))).

So there are 2*N flowers and N baskets.
He has to put all the flowers into the baskets and give her the final total cost.
But this total cost would be minimum.
Hence He has to minimize Summation ( c1+c2+c3+...+cn) , where ci is the cost of putting two flowers into ith basket.
ci = sqrt(square(x2-x1) + square((y2-y1)) , if two flowers at coordinates (x1,y1) and (x2,y2) are being put into ith basket

Input

First line gives the number of testcases 1 ≤ T ≤ 100.
Each case starts with an integer N (1 ≤ N ≤ 8). The next 2*N lines will give
the coordinates of a flower. Each line starts with the x coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000.

Output

For each case, output the minimum total cost, rounded to 2 decimal places. Follow the sample for exact format.

SAMPLE INPUT
3
1
9 9
10 10
2
0 0
1 0
4 1
5 1
5
10 10
20 10
5 5
1 1
120 3
6 6
50 60
3 24
6 9
0 0

SAMPLE OUTPUT
1.41
2.00
118.40

Explanation

For the first case we can just put both the flowers in the basket, so the cost will be sqrt((10-9)(10-9)+(10-9)(10-9))
For the second case we can put flower(0,0) and flower(1,0) in first basket, so c1 = sqrt((1-0)(1-0)+(0-0)(0-0)) and c2 = sqrt((5-4)(5-4)+(1-1)(1-1))
this (c1+c2) would be minimum.
but if we put let's say (0,0) and (4,1) in first and (1,0) and (5,1) in second, the (c1+c2) would not be minimum.

输入格式

见题面

输出格式

见题面

样例输入
100 8 645 848 376 242 334 860 554 445 644 459 770 121 493 651 411 716 494 515 562 789 834 587 547 176 875 925 380 276 24 285 250 235 8 22 379 530 245 997 4 362 956 257 748 326 980 547 504 863 950 466 944 124 52 834 786 277 909 598 238 953 224 660 898 583 830 2 527 610 269 796 987 177 322 447 1 198 463 699 92 5 53 267 491 439 843 236 803 23 688 907 718 557 198 591 397 977 992 281 10 867 6 722 623 648 189 20 709 151 275 147 944 109 796 509 849 982 103 599 900 389 637 466 788 214 523 8 11 210 638 319 238 570 990 622 167 40 726 824 93 258 234 244 658 792 122 944 652 745 599 509 982 392 204 429 559 637 183 363 5 809 607 42 529 42 759 352 173 352 892 939 15 175 260 189 132 518 536 788 747 8 276 630 786 249 92 267 433 194 265 531 319 40 300 746 493 26 249 616 560 554 904 606 179 446 377 190 164 455 566 418 661 90 6 168 878 982 565 989 953 372 569 447 775 669 372 887 649 385 364 127 776 884 537 224 505 734 856 1 852 971 995 370 5 328 611 109 892 279 145 690 415 477 769 56 937 434 504 618 732 800 415 676 174 8 824 658 665 57 305 522 122 938 399 410 287 474 357 53 595 870 837 698 795 3 406 309 534 341 399 19 464 143 819 600 400 499 6 931 243 549 973 828 504 499 844 700 366 120 228 838 50 217 748 501 822 495 971 543 126 135 18 1 476 566 471 313 8 480 535 763 271 467 516 375 357 231 719 327 609 282 904 922 923 753 700 284 902 153 54 564 105 527 881 555 920 644 68 10 163 7 911 34 70 955 533 929 873 983 907 76 856 863 168 768 709 950 541 390 660 529 191 799 0 503 995 491 628 843 2 960 693 708 540 321 566 740 729 6 843 872 310 658 163 816 285 153 504 944 680 859 168 830 23 677 97 781 928 696 880 673 135 445 4 603 39 127 744 440 679 784 893 221 856 713 570 517 86 164 468 8 245 660 251 313 134 480 822 50 738 427 941 303 342 360 71 988 119 348 501 21 672 108 942 85 266 41 797 926 116 969 361 138 4 688 411 891 211 31 429 502 502 563 289 789 733 609 439 524 445 2 947 572 868 720 814 327 516 907 5 659 254 744 775 899 963 231 602 361 351 162 472 601 631 449 85 2 44 177 149 7 241 477 644 69 66 877 862 476 605 966 280 148 325 746 134 648 796 578 526 110 593 553 405 10 715 355 241 240 6 590 807 697 754 888 902 839 706 913 804 100 326 338 287 480 792 542 462 274 951 408 569 641 314 6 214 434 442 484 350 613 341 691 87 108 488 491 947 796 405 942 193 967 958 304 691 96 760 245 8 168 675 561 330 577 65 398 482 242 757 425 450 890 303 861 260 528 741 357 754 42 419 692 413 652 574 839 290 324 509 509 978 5 545 110 624 199 575 698 393 376 860 771 103 423 600 798 430 301 62 254 747 498 4 594 913 933 37 79 566 308 654 73 373 12 857 982 717 67 908 4 963 748 742 739 779 220 243 741 301 811 798 110 30 204 614 0 4 552 468 89 749 615 524 446 154 961 234 873 856 701 71 16 808 1 652 9 400 104 7 11 873 409 779 550 458 320 275 966 381 294 11 396 753 167 318 454 271 643 21 335 737 205 481 754 72 930 629 4 405 324 185 703 282 952 933 357 337 125 747 165 709 911 833 152 2 466 877 767 974 898 121 385 504 3 657 496 35 12 970 971 146 945 934 993 960 801 6 780 187 20 254 44 573 890 358 510 21 673 216 532 645 837 463 966 53 461 296 346 577 108 762 1 190 684 154 833 4 746 539 690 974 526 427 131 116 761 572 477 420 300 456 274 734 7 462 183 192 254 733 256 874 810 350 51 91 616 592 24 851 923 126 191 115 281 843 498 313 714 712 293 448 211 6 299 288 827 95 603 714 461 713 419 702 216 102 523 848 932 93 605 161 366 622 547 778 509 645 3 742 982 277 126 864 693 302 687 419 781 361 954 2 18 387 874 438 925 177 24 909 8 684 232 627 145 773 951 579 860 458 546 578 301 553 769 572 83 188 364 839 924 981 892 150 980 780 669 520 40 760 266 707 778 4 338 146 70 344 754 815 796 241 163 293 374 852 13 997 605 302 5 91 584 771 234 426 757 324 237 222 634 522 586 120 525 962 898 679 683 898 540 5 671 899 92 727 643 511 43 9 371 805 718 553 56 34 27 875 875 858 481 182 4 696 15 477 320 434 736 784 32 713 286 924 955 439 965 552 818 3 737 393 613 960 507 969 373 99 711 67 983 863 2 106 530 1 746 858 955 563 685 8 135 165 895 5 240 814 654 736 812 604 137 221 379 744 737 609 303 549 655 88 384 458 550 296 961 486 433 24 573 340 424 43 8 119 199 401 472 848 112 383 577 829 211 478 908 700 898 114 118 529 922 404 432 940 279 354 358 919 894 181 903 934 873 243 487 8 495 487 481 772 602 430 265 695 389 362 489 853 182 492 594 438 736 302 133 477 492 15 778 627 641 290 866 920 569 809 752 804 7 854 685 691 933 875 300 192 265 291 66 795 396 512 242 701 786 677 385 875 654 847 245 426 344 224 659 979 591 5 338 919 508 544 922 652 455 551 841 32 591 663 703 829 892 844 776 766 150 947 3 889 539 946 519 693 373 374 677 734 795 52 477 8 154 812 313 576 602 659 17 720 581 792 815 132 798 225 946 104 607 975 272 605 702 312 400 60 256 275 895 682 117 201 904 653 8 130 937 254 350 693 996 247 613 509 172 519 859 456 9 444 626 73 997 592 540 241 887 415 447 985 640 959 806 891 93 33 227 3 692 959 449 519 378 935 223 789 196 983 58 471 6 73 73 769 911 217 463 397 485 204 636 471 897 644 117 474 18 866 918 44 592 763 269 63 803 6 177 362 896 619 227 968 373 536 275 575 976 97 726 740 666 134 598 221 466 154 923 830 392 208 2 896 542 449 186 623 646 43 637 4 168 236 974 314 98 864 953 451 502 415 361 366 942 163 646 99 4 616 103 208 430 140 731 774 30 673 886 790 484 921 690 376 260 3 220 405 565 418 57 270 689 532 945 131 25 43 4 25 787 263 385 686 318 998 452 926 432 269 371 756 701 334 121 2 307 700 965 736 940 813 701 958 4 984 669 564 666 319 829 63 508 966 737 713 975 677 253 353 12 3 184 313 881 491 640 550 798 827 215 637 896 690 6 820 379 410 198 487 283 23 388 261 548 542 744 498 360 794 637 501 617 795 950 316 344 784 890 8 573 726 596 35 144 177 88 681 112 394 42 790 634 978 345 883 76 447 533 151 634 524 37 268 216 590 300 991 681 932 668 732 1 942 203 690 62 2 694 275 435 857 795 727 608 33 4 873 380 472 240 850 229 836 43 764 897 483 482 858 454 911 240 7 543 890 285 194 600 59 799 324 380 199 57 620 204 524 971 695 99 889 386 601 8 186 177 551 404 275 752 803 6 491 261 923 786 91 560 971 143 366 388 530 99 387 506 923 320 649 487 726 995 844 962 246 413 6 959 707 529 174 447 779 295 693 851 516 408 544 366 46 579 179 139 511 327 102 600 854 890 259 2 556 482 582 576 456 314 942 227 3 487 27 678 338 235 800 291 738 618 586 279 505 5 513 663 634 226 128 642 764 819 832 697 763 25 66 612 271 856 916 359 475 79 3 638 96 283 417 556 387 744 729 490 37 969 409 6 714 770 424 481 605 283 337 805 601 280 357 999 794 919 528 818 485 994 797 61 806 517 107 14 2 698 124 967 163 147 699 167 17 1 590 972 89 426 6 175 80 951 698 513 195 351 353 69 594 269 146 765 514 683 524 266 643 511 332 222 233 738 470 5 22 372 867 587 600 128 757 951 118 397 735 704 777 503 760 967 657 835 81 574 7 795 276 71 392 105 552 616 969 846 603 861 193 517 903 574 818 540 496 507 389 99 452 902 372 769 604 296 442 4 491 390 280 373 68 581 90 518 393 516 617 543 233 753 442 485 2 494 255 551 207 845 244 658 547 3 948 971 70 304 5 772 831 431 130 675 324 949 1 143 102 370 331 6 289 856 129 314 578 450 23 17 745 196 787 487 585 868 770 438 830 632 778 63 502 224 563 155 4 181 690 724 568 403 22 655 186 810 62 237 249 91 66 530 455 2 34 197 312 853 236 2 579 615 3 716 312 306 786 311 346 520 392 429 87 685 505 7 901 648 569 70 743 911 392 722 473 291 217 211 808 348 275 998 38 518 747 723 172 828 145 141 384 363 714 473 3 67 894 658 434 865 891 748 444 184 146 192 422 3 88 72 633 242 952 732 950 531 422 963 171 950 8 846 126 808 328 729 202 706 132 859 272 350 714 793 911 726 998 510 486 62 311 981 914 197 625 242 852 776 340 134 572 913 196
样例输出
621.43 1266.34 1400.19 479.19 1371.55 1300.39 1810.18 400.56 1203.62 1376.63 973.25 1586.89 1184.81 1371.20 1130.16 513.25 1479.98 1735.64 532.86 1398.52 980.29 1002.20 1407.83 1368.59 1260.72 1521.65 1328.45 1629.73 1113.95 1264.67 1745.72 595.46 1768.06 1016.58 843.13 1006.64 1466.19 584.11 1397.77 1063.28 1366.19 1558.29 905.20 454.49 164.60 1219.89 1600.05 1281.75 1202.68 1269.53 1372.82 1183.60 796.39 1546.24 955.16 1381.99 1392.40 844.78 1137.79 978.08 822.97 1099.71 424.27 965.04 1605.54 1046.53 1126.77 1062.37 1086.25 911.32 1110.92 940.41 1253.99 847.37 1329.73 1336.60 186.08 709.89 1274.47 1436.16 1682.79 1262.47 1464.25 828.27 1057.95 1564.40 1178.98 340.14 886.05 1463.92 1041.35 813.54 710.09 486.01 835.92 1461.50 896.12 485.03 583.13 1067.27