use Data::Dumper;
use List::Util qw(max min sum);

my @testdata;
my $loop = <DATA>;
chomp $loop;

for ( my $i = 0; $i < 100; $i++ ) {
    my $cnt  = <DATA>;
    my $line = <DATA>;
    chomp $cnt;
    chomp $line;
    my @d = split / /, $line;
    push @testdata, \@d;
}

#warn Dumper @testdata;
#print Dumper all_half([100,101]);
#print Dumper remove_5or0( [ 100, 101 ] );

for my $e (@testdata) {
    my $depth = 1;
    my $flag  = [];
    make_tree( $e, [], $depth, $flag );
    my $min = min @$flag;
    print "$min\n";
}

sub make_tree {
    my $left  = shift;
    my $right = shift;
    my $depth = shift;
    my $flag  = shift;

    if ( !defined $left->[0] && !defined $right->[0] ) {

        #print "END left & right is NULL\n";
        return;
    }

    ## より深い木は探索しない
    my $min = min @$flag;
    if ( $depth > 0 && $min > 0 && $depth > $min ) {

        #print "END tree depth[$depth] min[$min]over\n";
        return;
    }

    ## error
    if ( $depth > 10000000 ) {
        print "error: $depth\n";
        exit;
    }

    ## 左要素を二分探索木を構築(remove,halfの順で)
    if ( defined $left->[0] ) {
        my @result;
        my $remove = remove_5or0($left);
        my $half   = all_half($left);
        my $cmp1   = join ':', @$left;
        my $cmp2   = join ':', @$remove;
        if ( defined $remove && $cmp1 ne $cmp2 ) {

            #print "L1: min=$min : depth=$depth : left=@$left -> remove=@$remove : half=@$half\n";
            make_tree( $remove, $half, $depth + 1, $flag );
        }
        elsif ( !defined $remove ) {
            push @$flag, $depth;

            #print "L2: min=$min : depth=$depth : left=@$left -> remove=@$remove : half=@$half\n";
            make_tree( $half, [], $depth + 1, $flag );
        }
        else {

            # "L3: min=$min : depth=$depth : left=@$left -> remove=@$remove : half=@$half\n";
            make_tree( $half, [], $depth + 1, $flag );
        }
    }
    ## 右要素を二分探索木を構築(remove,halfの順で)
    if ( defined $right->[0] ) {
        my @result;
        my $remove = remove_5or0($right);
        my $half   = all_half($right);
        my $cmp1   = join ':', @$right;
        my $cmp2   = join ':', @$remove;
        if ( defined $remove && $cmp1 ne $cmp2 ) {

            #print "R1: min=$min : depth=$depth : right=@$right -> remove=@$remove : half=@$half\n";
            make_tree( $remove, $half, $depth + 1, $flag );
        }
        elsif ( !defined $remove ) {
            push @$flag, $depth;

            #print "R2: min=$min : depth=$depth : right=@$right -> remove=@$remove : half=@$half\n";
            make_tree( $half, [], $depth + 1, $flag );
        }
        else {

            #print "R3: min=$min : depth=$depth : right=@$right -> remove=@$remove : half=@$half\n";
            make_tree( $half, [], $depth + 1, $flag );
        }
    }
}

sub remove_5or0 {
    my $data = shift;
    my @result;
    my $len = scalar @$data;
    for ( my $i = 0; $i < $len; $i++ ) {
        push @result, $data->[$i] if $data->[$i] % 5 != 0;
    }
    return defined @result ? \@result : undef;
}

sub all_half {
    my $data = shift;
    my @result;
    my $sum = 0;
    my $len = scalar @$data;
    for ( my $i = 0; $i < $len; $i++ ) {
        $sum += int $data->[$i] / 2;
        push @result, int $data->[$i] / 2;
    }
    return defined @result ? \@result : undef;
}

1;
__DATA__
100
2
10 11
3
0 9 9
4
81 67 83 86
3
11 22 30
1
0
1
5
1
999999
1
1000000
2
5 10
3
0 10 11
5
10 20 21 22 23
5
422808 211404 761062 845625 491519
5
77 6 62 98 79
5
12 25 23 92 59
5
46 86 5 21 2
5
0 94 81 88 53
5
85 82 97 65 21
5
5 69 2 9 6
5
69 0 86 81 79
5
74 6 24 23 33
5
100 39 10 97 63
5
36 24 70 34 100
10
38 6 27 37 98 0 15 99 63 7
10
2 97 77 18 42 55 2 62 58 26
10
61 79 99 91 72 59 58 40 76 26
10
58 47 50 17 46 48 67 20 32 1
10
48 72 30 42 58 12 39 36 67 24
10
22 51 96 88 39 65 31 83 99 80
10
90 71 34 20 7 7 82 70 55 3
10
72 60 6 3 98 0 52 16 98 19
10
68 28 51 90 77 27 45 14 62 18
10
79 25 48 15 59 67 79 13 0 25
5
816345 946844 812437 908335 963363
5
992246 994290 884290 981963 807035
5
934759 803243 953299 807061 854328
5
851822 819575 849849 963472 950074
5
823682 973962 869698 827792 923104
5
914249 983289 911566 869624 872028
5
857150 840785 899793 867303 880677
5
844750 929568 967812 837110 977675
5
821699 877306 982237 895499 853207
5
861246 929260 946378 925099 823621
10
890721 836002 861832 976902 975861 960958 947066 877196 918364 878220
10
961645 822922 918112 933455 891546 987312 927117 987916 918064 950629
10
978903 811788 900643 861268 931870 824836 834597 854455 891494 810755
10
938570 980416 994275 927415 933259 926646 940503 876967 897055 887909
10
814312 986293 951657 898363 979128 822377 894655 846200 873501 821819
10
843840 967764 836554 938520 837822 933615 837354 964377 983704 937903
10
897845 824664 850381 826360 874026 888004 907648 941666 835052 965905
10
957685 961357 867240 942002 811135 840764 927229 910218 871552 868986
10
922680 916258 872283 849776 901417 849951 880734 960358 802001 900087
10
929940 976208 836851 820451 836828 902428 964060 965610 827596 832039
10
84 64 62 860677 37 989668 927110 963088 16 967670
10
69 66 945163 955119 949831 84 874009 44 838879 30
10
810742 89 980493 928318 98 986950 8 828633 72 64
10
9 50 62 893080 65 982647 983288 44 933425 918956
10
997991 48 52 34 94 956285 847482 986479 863402 56
10
68 975148 20 100 943794 824792 844081 57 836031 74
10
801806 827413 947779 92 93 961872 83 9 67 851683
10
860361 22 905205 931004 19 825632 13 66 903993 35
10
990571 969004 985014 71 50 72 38 933425 27 907407
10
950484 804789 922769 67 40 24 14 61 851845 968061
10
819351 15 907753 997620 2 887527 88 89 900578 82
10
992074 50 977306 0 958967 816063 807739 15 86 9
10
989349 4 983839 990938 68 12 845417 866006 26 2
10
889048 41 56 51 821048 907676 936834 73 36 858718
10
3 857589 838342 899786 87 53 954373 929823 2 16
10
847779 888830 80 4 93 49 919195 98 909363 871017
10
820742 821875 57 47 54 822073 93 889898 63 888326
10
94 868969 65 11 974042 907852 100 6 860145 845162
10
956287 64 94 929494 948888 47 99 844062 885436 33
10
959761 3 955747 814370 958625 878958 71 22 78 22
10
397860 611230 33415 580570 731980 971795 154855 682035 30359 247765
9
583840 406910 619045 253586 380295 581100 576350 135450 125290
10
383340 868340 157652 979200 941500 699120 477025 336565 159780 583065
8
587955 939890 973190 113199 967165 988010 690120 772985
10
492500 9000 169155 271705 830215 702570 498235 829305 569565 130465
9
863270 628975 114410 331145 629240 834533 5845 285950 583655
8
189160 595245 558320 936395 190215 405792 212335 632758
8
705155 162870 7500 281400 757385 909090 273697 419015
7
378670 461265 764185 70895 116248 342055 951545
8
518405 147895 419275 926741 634655 602028 722105 44925
7
898100 680750 861273 407685 294720 879095 532240
10
602495 169775 430300 785750 479110 792055 684295 463595 35800 124990
7
347975 425552 247490 930575 498010 839866 796375
9
559980 791220 155116 476065 89515 126765 510440 185480 435959
9
326650 123047 244160 256200 22007 793528 386260 956985 732155
10
919570 524500 229210 80555 906235 704860 925530 68980 96460 804790
10
166990 47975 199845 333077 310215 243595 577195 277205 486 342960
9
332746 832945 273425 942209 732317 658625 24500 283640 477279
7
298647 408365 414025 449739 441280 230105 150610
8
247025 100470 322996 371545 22855 634485 762453 188660
9
145234 925138 556979 405625 476967 434115 609503 384823 951688
9
407356 46836 385027 864667 616812 826522 979291 28702 762148
6
960501 467878 869032 41082 735360 687205
9
411563 209151 837775 848189 135190 688703 495433 234093 531479
10
511582 921134 697374 314916 361923 703674 264227 21852 756704 18843
10
904798 411767 304543 329985 533909 955738 465184 289911 439608 17470
10
209151 752750 519734 269325 131165 860954 273338 938244 777983 901697
9
90766 857120 869596 983235 175896 413219 276847 859157 167701