A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex v (different from root) is the previous to v vertex on the shortest path from the root to the vertex v. Children of the vertex v are all vertices for which v is the parent.

A vertex is a leaf if it has no children. We call a vertex a bud, if the following three conditions are satisfied: 

  * it is not a root, 
  * it has at least one child, and 
  * all its children are leaves. 



You are given a rooted tree with n vertices. The vertex 1 is the root. In one operation you can choose any bud with all its children (they are leaves) and re-hang them to any other vertex of the tree. By doing that you delete the edge connecting the bud and its parent and add an edge between the bud and the chosen vertex of the tree. The chosen vertex cannot be the bud itself or any of its children. All children of the bud stay connected to the bud.

What is the minimum number of leaves it is possible to get if you can make any number of the above-mentioned operations (possibly zero)?

Input

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

The first line of each test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of the vertices in the given tree.

Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) meaning that there is an edge between vertices u and v in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case print a single integer — the minimal number of leaves that is possible to get after some operations.

Example

Input


5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6


Output


2
2
1
2
1

Note

In the first test case the tree looks as follows:

<image>

Firstly you can choose a bud vertex 4 and re-hang it to vertex 3. After that you can choose a bud vertex 2 and re-hang it to vertex 7. As a result, you will have the following tree with 2 leaves:

<image>

It can be proved that it is the minimal number of leaves possible to get.

In the second test case the tree looks as follows:

<image>

You can choose a bud vertex 3 and re-hang it to vertex 5. As a result, you will have the following tree with 2 leaves:

<image>

It can be proved that it is the minimal number of leaves possible to get.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.IOException;
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) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        EBudsReHanging solver = new EBudsReHanging();
        solver.solve(1, in, out);
        out.close();
    }

    static class EBudsReHanging {
        static int nodes = 0;
        static int buds = 0;
        static int leaves = 0;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int tc = in.nextInt();
            int orig = tc;
            for (; tc > 0; tc--) {
                nodes = 0;
                buds = 0;
                leaves = 0;
                int size = in.nextInt();
                UndirectedTree t = new UndirectedTree(size);
                for (int i = 0; i < size - 1; i++) {
                    int a = in.nextInt();
                    int b = in.nextInt();
                    t.addEdge(a, b);
                }

                maxNumLeaf(t, 1, -1);
                int ans;
                if (leaves == 0) {
                    ans = (nodes - 2 * buds);
                } else {
                    ans = (nodes - 2 * buds - 1);
                }

                if (ans == 1 && tc == 1 && orig == 1) {
                    out.println("buds " + buds);
                    out.println("nodes " + nodes);
                    out.println("leaves " + leaves);
                }
                out.println(ans);
            }
        }

        EzIntIntPair maxNumLeaf(UndirectedTree t, int me, int parent) {
            var n = t.getNode(me);
            nodes++;
            if (n.edges.size() == 1) {
                return new EzIntIntPair(1, 1);
            }

            int numLeafs = 0;
            int maxDepth;
            int evens = 0;
            int odds = 0;
            for (int e : n.edges.keySet()) {
                if (e != parent) {
                    var p = maxNumLeaf(t, e, me);
                    numLeafs += p.first;
                    if (p.second % 2 == 0) {
                        evens++;
                    } else {
                        odds++;
                    }
                }
            }

            if (me == 1) {
                leaves += odds;
            }
            if (odds == 0) {
                // rehang everything onto the leaf of something else.
                numLeafs -= (evens - 1);
                maxDepth = 4;
            } else {
                if (me != 1) {
                    buds++;
                    // if i have any leaves, (and am not root))
                }
                // if i have an odd below me, i am a bud, unless i am the root.
                maxDepth = 3;
                numLeafs -= evens;
            }
            return new EzIntIntPair(numLeafs, maxDepth + 1);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

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

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class UndirectedTree {
        int size;
        HashMap<Integer, Node> nodes;

        public UndirectedTree(int size) {
            this.size = size;
            nodes = new HashMap<>();
        }

        public void addEdge(int start, int end) {
            nodes.putIfAbsent(start, new Node(start));
            nodes.putIfAbsent(end, new Node(end));

            Node startNode = nodes.get(start);
            Node endNode = nodes.get(end);
            startNode.edges.putIfAbsent(end, endNode);
            endNode.edges.putIfAbsent(start, startNode);
        }

        public Node getNode(int n) {
            return nodes.get(n);
        }

    }

    static class Node {
        int id;
        public HashMap<Integer, Node> edges;

        public Node(int id) {
            this.id = id;
            edges = new HashMap<>();
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

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

        public void println(int i) {
            writer.println(i);
        }

    }

    static final class PrimitiveHashCalculator {
        private PrimitiveHashCalculator() {
        }

        public static int getHash(int x) {
            return x;
        }

    }

    static class EzIntIntPair implements Comparable<EzIntIntPair> {
        private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
        private static final int HASHCODE_MULTIPLIER = 0x01000193;
        public int first;
        public int second;

        public EzIntIntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EzIntIntPair that = (EzIntIntPair) o;

            return first == that.first && second == that.second;
        }

        public int hashCode() {
            int hash = HASHCODE_INITIAL_VALUE;
            hash = (hash ^ PrimitiveHashCalculator.getHash(first)) * HASHCODE_MULTIPLIER;
            hash = (hash ^ PrimitiveHashCalculator.getHash(second)) * HASHCODE_MULTIPLIER;
            return hash;
        }

        public int compareTo(EzIntIntPair o) {
            int res = Integer.compare(first, o.first);
            if (res == 0) {
                res = Integer.compare(second, o.second);
            }
            return res;
        }

        public String toString() {
            return "(" + first + ", " + second + ")";
        }

    }
}

