P14944 [HackerEarth] There is a street by the name of colourful street in Cape Town. The residents of the place have decided that they will paint their cars in either Red, Black or Yellow colour and not othe
普及
题目描述

There is a street by the name of colourful street in Cape Town. The residents of the place have decided that they will paint their cars in either Red, Black or Yellow colour and not other. They have also decided that no two adjacent cars, when kept in the houses, will have the same colour. For cars i, i-1 and i+1 are the neighbours and note that the first and the last cars are not neighbours.

The cost of painting a car in a particular colour is different. The cost of painting the first car in colour red maybe different than what its for painting the second car in the same colour.

You have to find the minimum of cost of painting the cars which satisfy the given condition.

Constraints:
1 ≤ N ≤ 20
1 ≤ cost ≤ 1000

Input:
The first line will contain the number of testcases, T. The second line will contain an integer N that will specify how many cars are there. Each of the following N lines will contain 3 numbers separated by space that represents the cost of painting that cars in either red, black or yellow colour respectively.

Output:
Print T lines showing the cost of painting the cars for each testcase.

SAMPLE INPUT
1
2
11 12 13
14 15 16

SAMPLE OUTPUT
26

Explanation

The first car should be painted in Red (11), the second should be painted in Black (15).
So the total cost becomes 11+15 = 26

输入格式

见题面

输出格式

见题面

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