Polycarp came up with a new programming language. There are only two types of statements in it: 

  * "x := s": assign the variable named x the value s (where s is a string). For example, the statement var := hello assigns the variable named var the value hello. Note that s is the value of a string, not the name of a variable. Between the variable name, the := operator and the string contains exactly one space each.
  * "x = a + b": assign the variable named x the concatenation of values of two variables a and b. For example, if the program consists of three statements a := hello, b := world, c = a + b, then the variable c will contain the string helloworld. It is guaranteed that the program is correct and the variables a and b were previously defined. There is exactly one space between the variable names and the = and + operators. 



All variable names and strings only consist of lowercase letters of the English alphabet and do not exceed 5 characters.

The result of the program is the number of occurrences of string haha in the string that was written to the variable in the last statement.

Polycarp was very tired while inventing that language. He asks you to implement it. Your task is — for given program statements calculate the number of occurrences of string haha in the last assigned variable.

Input

The first line contains an integer t (1 ≤ t ≤ 10^3). Then t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 50) — the number of statements in the program. All variable names and strings are guaranteed to consist only of lowercase letters of the English alphabet and do not exceed 5 characters.

This is followed by n lines describing the statements in the format described above. It is guaranteed that the program is correct.

Output

For each set of input data, output the number of occurrences of the haha substring in the string that was written to the variable in the last statement.

Example

Input


4
6
a := h
b := aha
c = a + b
c = c + c
e = c + c
d = a + c
15
x := haha
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
1
haha := hah
5
haahh := aaaha
ahhhh = haahh + haahh
haahh = haahh + haahh
ahhhh = ahhhh + haahh
ahhaa = haahh + ahhhh


Output


3
32767
0
0

Note

In the first test case the resulting value of d is hhahahaha.
import java.io.*;
import java.util.*;

public class Main {
    private static FastScanner in;
    private static PrintWriter out;

    public static void main (String[] args) throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            in = new FastScanner(new FileInputStream("input.txt"));
            out = new PrintWriter("output.txt");
        } else {
            in = new FastScanner();
            out = new PrintWriter(System.out);
        }

        int nTest = 1;
        nTest = in.nextInt();
        for (int testcase = 1; testcase <= nTest; ++testcase) {
            solve();
        }
        out.flush();
    }

    private static final String pattern = "haha";

    static class Node {
        private long cnt;
        private String left, right;

        Node (String s) {
            this.cnt = countMatches(s);
            if (s.length() < pattern.length()) {
                this.left = this.right = s;
            } else {
                this.left = s.substring(0, pattern.length());
                this.right = s.substring(s.length() - pattern.length());
            }
        }

        Node (long cnt, String left, String right) {
            this.cnt = cnt;
            this.left = left;
            this.right = right;
        }

        public long count () {
            return this.cnt;
        }

        public String right () {
            return this.right;
        }

        public String left () {
            return this.left;
        }
    }

    static Node merge (Node a, Node b) {
        long cnt = a.count() + b.count();
        String L = a.right(), R = b.left();
        for (int left = Math.max(1, pattern.length() - R.length()); left <= pattern.length() - 1 && left <= L.length(); ++left) {
            if (L.substring(L.length() - left).equals(pattern.substring(0, left)) &&
                R.substring(0, pattern.length() - left).equals(pattern.substring(left))) {
                ++cnt;
            }
        }
        L = a.left(); R = b.right();
        if (L.length() < pattern.length()) {
            L += b.left();
            if (L.length() > pattern.length()) {
                L = L.substring(0, pattern.length());
            }
        }
        if (R.length() < pattern.length()) {
            R = a.right() + R;
            if (R.length() > pattern.length()) {
                R = R.substring(R.length() - pattern.length());
            }
        }
        return new Node(cnt, L, R);
    }

    static long countMatches (String s) {
        long cnt = 0;
        for (int i = 0; i + 3 < s.length(); ++i) {
            char ch = s.charAt(i);
            if (s.substring(i, i + 4).equals(pattern)) {
                ++cnt;
            }
        }
        return cnt;
    }

    static void solve () throws IOException {
        int n = in.nextInt();
        HashMap<String, Node> value = new HashMap<>();
        String variableName = new String("");
        while (n --> 0) {
            String input = in.nextLine();
            StringBuffer name = new StringBuffer();
            for (int i = 0; i < input.length(); ++i) {
                char ch = input.charAt(i);
                if (ch == ':') {
                    variableName = name.toString();
                    value.put(variableName, new Node(input.substring(i + 3)));
                    break;
                } else if (ch == '=') {
                    variableName = name.toString();
                    name = new StringBuffer("");
                    for (int j = i + 2; j < input.length(); ++j) {
                        ch = input.charAt(j);
                        if (ch == ' ') {
                            String var1 = name.toString();
                            String var2 = input.substring(j + 3);
                            value.put(variableName, merge(value.get(var1), value.get(var2)));
                            break;
                        } else {
                            name.append(ch);
                        }
                    }
                    break;
                } else if (ch != ' ') {
                    name.append(ch);
                }
            }
        }
        out.println(value.get(variableName).count());
    }
    //TODO: Change length acc to max length of input string in nextLine()

    // ----------------- SORT -------------------
    static void sort (int[] a) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int val : a) {
            arr.add(val);
        }
        Collections.sort(arr);
        for (int i = 0; i < a.length; ++i) {
            a[i] = arr.get(i);
        }
    }

    // --------------------- I/O ---------------------
    static class FastScanner {
        private static BufferedInputStream bin;
        final private int N = 1 << 13;
        private byte[] buf;
        private int ptr, siz;

        FastScanner () throws IOException {
            bin = new BufferedInputStream(System.in);
            buf = new byte[N];
            ptr = siz = 0;
        }

        FastScanner (FileInputStream in) throws IOException {
            bin = new BufferedInputStream(in);
            buf = new byte[N];
            ptr = siz = 0;
        }

        private void fill () throws IOException {
            siz = bin.read(buf, 0, N);
            if (siz == -1) {
                buf[0] = -1;
            }
        }

        private byte read () throws IOException {
            if (ptr == siz) {
                fill();
                ptr = 0;
            }
            return buf[ptr++];
        }

        private boolean isWhiteSpace (byte c) {
            return c == ' ' || c == '\n' || c == '\t' || c == '\r';
        }

        public String nextLine () throws IOException {
            final int maxLength = 1000 + 5;
            byte[] s = new byte[maxLength];
            byte c = read();
            int len = 0;
            while (isWhiteSpace(c)) {
                c = read();
            }
            for (; c != -1 && c != '\n' && c != '\r'; c = read()) {
                s[len++] = c;
            }
            return new String(s, 0, len);
        }

        public int nextInt () throws IOException {
            int res = 0;
            byte c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            boolean neg = false;
            if (c == '-') {
                neg = true;
                c = read();
            }
            for (; c >= '0' && c <= '9'; c = read()) {
                res = res * 10 + c - '0';
            }
            return neg ? -res : res;
        }

        public long nextLong () throws IOException {
            long res = 0;
            byte c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            boolean neg = false;
            if (c == '-') {
                neg = true;
                c = read();
            }
            for (; c >= '0' && c <= '9'; c = read()) {
                res = res * 10 + c - '0';
            }
            return neg ? -res : res;
        }

        public double nextDouble () throws IOException {
            double res = 0, div = 1;
            byte c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            boolean neg = false;
            if (c == '-') {
                neg = true;
                c = read();
            }
            for (; c >= '0' && c <= '9'; c = read()) {
                res = res * 10 + c - '0';
            }
            if (c == '.') {
                for (c = read(); c >= '0' && c <= '9'; c = read()) {
                    res += (c - '0') / div;
                    div *= 10;
                }
            }
            return neg ? -res : res;
        }
    }
}