To help those contestants who struggle a lot in contests, the headquarters of Codeforces are planning to introduce Division 5. In this new division, the tags of all problems will be announced prior to the round to help the contestants.

The contest consists of n problems, where the tag of the i-th problem is denoted by an integer a_i.

You want to AK (solve all problems). To do that, you must solve the problems in some order. To make the contest funnier, you created extra limitations on yourself. You do not want to solve two problems consecutively with the same tag since it is boring. Also, you are afraid of big jumps in difficulties while solving them, so you want to minimize the number of times that you solve two problems consecutively that are not adjacent in the contest order.

Formally, your solve order can be described by a permutation p of length n. The cost of a permutation is defined as the number of indices i (1≤ i<n) where |p_{i+1}-p_i|>1. You have the requirement that a_{p_i}≠ a_{p_{i+1}} for all 1≤ i< n.

You want to know the minimum possible cost of permutation that satisfies the requirement. If no permutations meet this requirement, you should report about it.

Input

The first line contains a single integer t (1≤ t≤ 10^4) — the number of test cases.

The first line of the description of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the number of problems in the contest.

The next line contains n integers a_1,a_2,… a_n (1 ≤ a_i ≤ n) — the tags of the problems.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, if there are no permutations that satisfy the required condition, print -1. Otherwise, print the minimum possible cost of a permutation that satisfies the required condition.

Example

Input


4
6
2 1 2 3 1 1
5
1 1 1 2 2
8
7 7 2 7 7 1 8 7
10
1 2 3 4 1 1 2 3 4 1


Output


1
3
-1
2

Note

In the first test case, let p=[5, 4, 3, 2, 1, 6]. The cost is 1 because we jump from p_5=1 to p_6=6, and |6-1|>1. This permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than 1.

In the second test case, let p=[1,5,2,4,3]. The cost is 3 because |p_2-p_1|>1, |p_3-p_2|>1, and |p_4-p_3|>1. The permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than 3.

In the third test case, for any order of solving the problems, we will solve two problems with the same tag consecutively, so the answer is -1.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            FTheStrugglingContestant solver = new FTheStrugglingContestant();
            int testCount = Integer.parseInt(in.next());
            for (int i = 1; i <= testCount; i++)
                solver.solve(i, in, out);
            out.close();
        }
    }

    static class FTheStrugglingContestant {
        Debug debug = new Debug(true);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int[] a = new int[n];
            in.populate(a);
            EndPoint[] eps = new EndPoint[n + 1];
            for (int i = 0; i <= n; i++) {
                eps[i] = new EndPoint();
                eps[i].v = i;
            }
            for (int i = 1; i < n; i++) {
                if (a[i - 1] == a[i]) {
                    eps[a[i]].cnt++;
                    eps[a[i - 1]].cnt++;
                }
            }
            eps[a[0]].cnt++;
            eps[a[n - 1]].cnt++;
            Arrays.sort(eps, (x, y) -> Integer.compare(x.cnt, y.cnt));
            SequenceUtils.reverse(eps);

            int sum = 0;
            for (EndPoint ep : eps) {
                sum += ep.cnt;
            }
            int max = eps[0].cnt;
            int maxV = eps[0].v;
            debug.debug("sum", sum);
            debug.debug("max", max);
            debug.debug("maxV", maxV);
            for (int i = 1; i < n; i++) {
                if (max - 2 > sum - max && a[i - 1] != a[i] && a[i - 1] != maxV &&
                        a[i] != maxV) {
                    sum += 2;
                }
            }
            if (max - 2 > sum - max) {
                out.println(-1);
            } else {
                out.println((sum - 2) / 2);
            }
        }

    }

    static class EndPoint {
        int v;
        int cnt;

    }

    static class SequenceUtils {
        public static <T> void swap(T[] data, int i, int j) {
            T tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static <T> void reverse(T[] data) {
            reverse(data, 0, data.length - 1);
        }

        public static <T> void reverse(T[] data, int l, int r) {
            while (l < r) {
                swap(data, l, r);
                l++;
                r--;
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String next() {
            return readString();
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, int x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

    }
}

