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.util.Arrays;
import java.nio.CharBuffer;
import java.io.IOException;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.StandardCharsets;
import java.nio.ByteBuffer;
import java.io.UncheckedIOException;
import java.nio.charset.Charset;
import java.io.Writer;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner2 in = new LightScanner2(inputStream);
        LightWriter2 out = new LightWriter2(outputStream);
        FTheStrugglingContestant solver = new FTheStrugglingContestant();
        solver.solve(1, in, out);
        out.close();
    }

    static class FTheStrugglingContestant {
        public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {
            int testCases = in.ints();
            testcase:
            for (int testCase = 1; testCase <= testCases; testCase++) {
                int n = in.ints();
                int[] a = in.ints(n);
                int[] counter = new int[n];
                for (int i = 0; i < n; i++) counter[--a[i]]++;
                for (int i = 0; i < n; i++) {
                    if (counter[i] > (n + 1) / 2) {
                        out.ans(-1).ln();
                        continue testcase;
                    }
                }

                int cnt = 0, dec = 0;
                int[] invalids = new int[n];
                for (int i = 1; i < n; i++) {
                    if (a[i - 1] == a[i]) {
                        cnt++;
                        invalids[a[i]]++;
                    } else dec++;
                }
                int k = 0;
                for (int i = 0; i < n; i++) {
                    if (invalids[k] < invalids[i]) k = i;
                }
                if (invalids[k] * 2 <= cnt) {
                    out.ans(cnt).ln();
                    continue testcase;
                }
                int resolve = invalids[k] * 2 - cnt;
                if (a[0] != k) resolve--;
                if (a[n - 1] != k) resolve--;
                out.ans(cnt + Math.max(0, resolve)).ln();
            }
        }

    }

    static class LightWriter2 implements AutoCloseable {
        private static final int BUF_SIZE = 16 * 1024;
        private final OutputStream out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter2(OutputStream out) {
            this.out = out;
        }

        public LightWriter2(Writer out) {
            this.out = new LightWriter2.WriterOutputStream(out);
        }

        private void allocate(int n) {
            if (ptr + n <= BUF_SIZE) return;
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");
        }

        public void close() {
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.flush();
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private static int countDigits(int l) {
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        public LightWriter2 ans(int x) {
            allocate(12);
            if (!breaked) buf[ptr++] = ' ';
            breaked = false;

            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            int n = countDigits(x);
            for (int i = ptr + n - 1; ptr <= i; i--) {
                buf[i] = (byte) (x % 10 + '0');
                x /= 10;
            }
            ptr += n;

            return this;
        }

        public LightWriter2 ln() {
            allocate(1);
            buf[ptr++] = '\n';
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        private static class WriterOutputStream extends OutputStream {
            final Writer writer;
            final CharsetDecoder decoder;

            WriterOutputStream(Writer writer) {
                this.writer = writer;
                this.decoder = StandardCharsets.UTF_8.newDecoder();
            }

            public void write(int b) throws IOException {
                writer.write(b);
            }

            public void write(byte[] b) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b)).array());
            }

            public void write(byte[] b, int off, int len) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());
            }

            public void flush() throws IOException {
                writer.flush();
            }

            public void close() throws IOException {
                writer.close();
            }

        }

    }

    static class LightScanner2 extends LightScannerAdapter {
        private static final int BUF_SIZE = 16 * 1024;
        private final InputStream stream;
        private final StringBuilder builder = new StringBuilder();
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private int len;

        public LightScanner2(InputStream stream) {
            this.stream = stream;
        }

        private int read() {
            if (ptr < len) return buf[ptr++];
            reload();
            if (len == -1) return -1;
            return buf[ptr++];
        }

        private void reload() {
            try {
                ptr = 0;
                len = stream.read(buf);
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void load(int n) {
            if (ptr + n <= len) return;
            System.arraycopy(buf, ptr, buf, 0, len - ptr);
            len -= ptr;
            ptr = 0;
            try {
                int r = stream.read(buf, len, BUF_SIZE - len);
                if (r == -1) return;
                len += r;
                if (len != BUF_SIZE) buf[len] = '\n';
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void skip() {
            while (len != -1) {
                while (ptr < len && isTokenSeparator(buf[ptr])) ptr++;
                if (ptr < len) return;
                reload();
            }
            throw new NoSuchElementException("EOF");
        }

        private void loadToken() {
            builder.setLength(0);
            skip();
            for (int b = read(); !isTokenSeparator(b); b = read()) {
                builder.appendCodePoint(b);
            }
        }

        public String string() {
            loadToken();
            return builder.toString();
        }

        public int ints() {
            skip();
            load(12);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            int x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + ((char) b) + "'");
            }
            return negate ? -x : x;
        }

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

        private static boolean isTokenSeparator(int b) {
            return b < 33 || 126 < b;
        }

    }

    static abstract class LightScannerAdapter implements AutoCloseable {
        public abstract String string();

        public int ints() {
            return Integer.parseInt(string());
        }

        public final int[] ints(int length) {
            int[] res = new int[length];
            Arrays.setAll(res, ignored -> ints());
            return res;
        }

        public abstract void close();

    }
}

