1197_A. DIY Wooden Ladder_28853
Let's denote a k-step ladder as the following structure: exactly k + 2 wooden planks, of which

  * two planks of length at least k+1 — the base of the ladder; 
  * k planks of length at least 1 — the steps of the ladder; 



Note that neither the base planks, nor the steps planks are required to be equal.

For example, ladders 1 and 3 are correct 2-step ladders and ladder 2 is a correct 1-step ladder. On the first picture the lengths of planks are [3, 3] for the base and [1] for the step. On the second picture lengths are [3, 3] for the base and [2] for the step. On the third picture lengths are [3, 4] for the base and [2, 3] for the steps. 

<image>

You have n planks. The length of the i-th planks is a_i. You don't have a saw, so you can't cut the planks you have. Though you have a hammer and nails, so you can assemble the improvised "ladder" from the planks.

The question is: what is the maximum number k such that you can choose some subset of the given planks and assemble a k-step ladder using them?

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of queries. The queries are independent.

Each query consists of two lines. The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of planks you have.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^5) — the lengths of the corresponding planks.

It's guaranteed that the total number of planks from all queries doesn't exceed 10^5.

Output

Print T integers — one per query. The i-th integer is the maximum number k, such that you can choose some subset of the planks given in the i-th query and assemble a k-step ladder using them.

Print 0 if you can't make even 1-step ladder from the given set of planks.

Example

Input


4
4
1 3 1 3
3
3 3 2
5
2 3 3 4 2
3
1 1 2


Output


2
1
2
0

Note

Examples for the queries 1-3 are shown at the image in the legend section.

The Russian meme to express the quality of the ladders:

<image>
t = int(raw_input())
for i in range(t):
    size = 0
    n = int(raw_input())

    #print "Case ", i
    planks = map(int, raw_input().split())
    if n < 3:
        print size
        continue

    #print "debug:",n, planks
    planks.sort(reverse=True)
    if planks[1] > 1:
        max_size = planks[1] - 1
        poss = n-2
        if poss > max_size:
            print max_size
        else:
            print poss
    else:
        print 0





4
4
1 3 1 3
3
3 3 2
5
2 3 3 4 2
3
1 1 2
 1
6
1 1 3 2 10000 1000
 2
3
1 2 3
6
1 1 3 2 10000 1000
 1
9
3 3 3 3 3 3 3 3 4
 1
6
100 50 50 50 50 50
 2
3
1 2 0
6
1 1 3 2 10000 1000
 1
9
3 3 3 3 3 3 5 3 4
 1
6
100 50 50 50 77 50
 4
4
1 4 1 3
3
3 3 2
5
2 3 3 4 2
3
1 1 2
 1
9
3 3 3 6 3 6 4 3 4
 4
4
1 8 1 3
3
1 3 1
5
2 1 3 4 2
3
1 1 2
 4
4
1 8 1 3
3
1 3 1
5
2 1 3 4 2
3
1 2 2
 4
4
1 3 1 3
3
3 3 2
5
2 3 5 4 2
3
1 1 2
 4
4
1 4 1 3
3
3 3 1
5
2 3 3 4 2
3
2 1 2
 1
9
3 3 3 3 3 3 2 3 4
 4
4
1 12 1 3
3
1 3 1
5
2 1 3 1 2
3
1 1 2
 2
3
1 2 0
6
1 1 3 2 10000 1100
 1
9
3 3 3 3 3 3 5 5 4
 1
6
100 50 99 50 77 50
 4
4
1 4 1 3
3
3 3 1
5
2 3 3 4 2
3
1 1 2
 2
3
1 2 0
6
1 1 2 2 10000 1100
 1
9
3 3 3 3 3 6 5 5 4
 2
3
1 2 0
6
1 1 2 2 10000 0100
 2
3
1 2 0
6
1 1 2 4 10000 0100
 1
6
1 1 5 2 10000 1000
 2
3
1 2 1
6
1 1 3 2 10000 1000
 1
9
3 3 3 3 3 3 4 3 4
 1
6
100 25 50 50 50 50
 1
9
3 3 3 3 3 4 5 3 4
 2
3
1 2 0
6
1 1 3 1 10000 1100
 1
6
100 50 193 50 77 50
 4
4
1 4 1 3
3
3 3 1
5
2 1 3 4 2
3
1 1 2
 2
3
1 2 0
6
1 1 4 2 10000 1100
 1
6
1 1 5 3 10000 1000
 1
9
3 3 3 6 3 3 4 3 4
 1
6
100 15 50 50 50 50
 2
3
1 2 -1
6
1 1 3 1 10000 1100
 1
6
100 50 10 50 77 50
 4
4
1 8 1 3
3
3 3 1
5
2 1 3 4 2
3
1 1 2
 1
6
100 50 10 12 77 50
 1
9
3 3 3 6 3 6 6 3 4
 1
6
100 50 14 12 77 50
 1
6
100 50 14 17 77 50
 1
6
100 50 14 17 77 100
 1
6
100 93 14 17 77 100
 1
6
100 93 14 16 77 100
 1
6
100 93 16 16 77 100
 1
6
100 93 16 4 77 100
 1
6
100 93 19 4 77 100
 1
6
100 93 19 4 77 101
 1
6
1 1 3 2 11000 1000
 2
3
1 2 0
6
1 1 6 2 10000 1000
 1
6
100 50 50 26 77 50
 4
4
1 4 1 3
3
3 3 1
5
2 3 3 8 2
3
1 1 2
 1
6
100 50 99 29 77 50
 2
3
1 2 0
6
1 1 2 2 10000 1000
 1
9
3 3 3 3 3 6 5 2 4
 2
3
1 2 -1
6
1 1 2 2 10000 0100
 2
3
1 2 1
6
1 1 3 2 10000 1001
 1
6
100 47 50 50 50 50
 1
6
100 50 193 50 77 94
 2
3
1 2 0
6
1 2 4 2 10000 1100
 1
6
1 1 2 3 10000 1000
 1
6
100 16 50 50 50 50
 2
3
1 2 -1
6
1 1 3 1 10000 0100
 1
6
100 36 10 50 77 50
 4
4
1 8 1 3
3
3 3 1
5
2 1 4 4 2
3
1 1 2
 1
9
3 3 3 6 3 6 2 3 4
 4
4
1 12 1 3
3
1 3 1
5
2 1 3 4 2
3
1 1 2
 1
9
3 3 3 8 3 6 6 3 4
 1
6
100 50 25 12 77 50
 1
6
100 50 10 17 77 50
 1
6
100 50 14 2 77 100
 1
6
100 93 5 16 77 100
 1
6
101 93 16 16 77 100
 1
6
100 93 35 4 77 100
 1
6
110 93 19 4 77 101
 1
6
1 1 3 2 11000 1010
 4
4
1 3 1 3
3
3 3 2
5
2 3 5 4 2
3
1 1 3
 2
3
1 2 0
6
1 1 6 2 10000 1001
 4
4
1 4 1 3
3
3 3 1
5
2 3 3 8 4
3
1 1 2
 1
6
110 50 99 29 77 50
 4
4
1 4 1 3
3
3 3 1
5
2 3 3 4 2
3
2 1 0
 2
3
1 2 1
6
1 1 2 2 10000 1000
 1
9
3 6 3 3 3 6 5 2 4
 2
3
1 2 -1
6
1 1 2 2 10100 0100
 2
3
1 2 1
6
1 1 3 3 10000 1001
 1
6
100 56 50 50 50 50
 1
6
100 50 375 50 77 94
 2
3
1 2 0
6
1 2 6 2 10000 1100
 1
6
101 16 50 50 50 50
 1
6
100 36 10 16 77 50
 1
9
4 3 3 8 3 6 6 3 4
 1
6
100 50 25 12 39 50
 1
6
100 71 10 17 77 50
 1
6
100 50 16 2 77 100
 1
6
111 93 16 16 77 100
 1
6
110 27 19 4 77 101
 1
6
1 1 3 2 11000 1110

2
1
2
0
 4
 1
4
 2
 4
 0
4
 3
 4
 2
1
2
0
 5
 2
0
2
0
 2
0
2
1
 2
1
3
0
 2
1
2
1
 2
 2
0
1
0
 0
4
 4
 4
 2
1
2
0
 0
4
 4
 0
4
 0
4
 4
 0
4
 3
 4
 3
 0
4
 4
 2
1
2
0
 0
4
 4
 3
 4
 0
4
 4
 2
1
2
0
 4
 5
 4
 4
 4
 4
 4
 4
 4
 4
 4
 4
 0
4
 4
 2
1
2
0
 4
 0
4
 4
 0
4
 0
4
 4
 4
 0
4
 4
 4
 0
4
 4
 2
1
3
0
 5
 2
0
2
0
 5
 4
 4
 4
 4
 4
 4
 4
 4
 2
1
3
0
 0
4
 2
1
3
0
 4
 2
1
2
0
 0
4
 5
 0
4
 0
4
 4
 4
 0
4
 4
 4
 5
 4
 4
 4
 4
 4
 4
