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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class N725 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>tmp;
	static boolean[]v;
	static int[]c,d;
	static int[][]dp;
	static char[][]mp;
	static int A,B,n,m,h,ans;
	static String a,b;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		//B();
	    //C();
//	    D();
		// D2();
		E();
		//F();
		//G();
		out.close();
	}
	  private static void A() throws IOException {
		  	int t=ni();
			while(t-->0) {
				n=ni();
				int[]a=nai(n);
				int mnid=0,mxidx=0;
				for(int i=0;i<n;i++) {
					if(a[mnid]>a[i])mnid=i;
					if(a[mxidx]<a[i])mxidx=i;
				}
				int ans=Math.min(Math.max(mnid, mxidx)+1, n-Math.min(mnid, mxidx));
				int mnn=Math.min(mnid, mxidx);
				int mxx=Math.max(mnid, mxidx);
				ans=Math.min(ans, mnn+1+n-mxx);
				ol(ans);
			}
		
	   }
		static void B() throws IOException {
			int t=ni();
			while(t-->0) {
				n=ni();
				int[]a=nai(n);
				boolean same=true;
				int sum=a[0];
				for(int i=1;i<n;i++) {
					if(a[i]!=a[i-1])same=false;
					sum+=a[i];
				}
				if(same) {
					ol(0);continue;
				}
				if(sum%n!=0) {
					ol(-1);continue;
				}
				int trgt=sum/n;
				int ans=0;
				for(int i=0;i<n;i++) {
					if(a[i]>trgt)ans++;
				}
				ol(ans);
			}
		}
		public static int getMoreEq(int i,Long[]a,long k) {
			int st=i+1,end=a.length-1;
			if(a[st]>=k)return st;
			if(a[end]<k)return -1;
			while(end-st>1) {
				int mid=(end+st)/2;//remove 1 maybe?
				if(a[mid]>=k)
					end=mid;
				else
					st=mid;
			}
			return end;

		}
		public static int getLessEq(int i,Long[]a,long k) {
			int st=i+1,end=a.length-1;
			if(a[end]<=k)return end;
			if(a[st]>k)return -1;
			while(end-st>1) {
				int mid=(end+st)/2;//remove 1 maybe?
			    if(a[mid]<=k)
					st=mid;
				else
					end=mid;
			}
			return st;
		}
		static void C() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 int n=ni();
				 long l=nl(),r=nl();
				 Long a[]=new Long[n];
				 for(int i=0;i<n;i++)a[i]=nl();
				 Arrays.sort(a);
				 long ans=0l;
				 for(int i=0;i<n-1;i++) {
					 long cur=a[i];
					 long trgt1=l-cur,trgt2=r-cur;
					 int idx1=getMoreEq(i, a, trgt1);
					 int idx2=getLessEq(i, a, trgt2);
					 if(idx1==-1||idx2==-1)continue;
					 ans+=(Math.max(idx2-idx1+1, 0));
				 }
				 ol(""+ans);
			 }
		}
		static ArrayList<Integer>primes;
		static void sieve(int N)
		{
			primes = new ArrayList<Integer>();
			boolean[] isComposite = new boolean[N];
			for(int i = 2; i < N; ++i)
				if(!isComposite[i])
				{
					primes.add(i);
					if(1l*i*i<N) {
					for(int j = i * i; j < N; j += i)
						isComposite[j] = true;
					}
				}
		}
		static int gcd (int a, int b) {
		    return b==0?a:gcd (b, a % b);
		}
		static void D2() throws IOException {
			int t=ni();
			sieve(40000);
			while(t-->0) {
				int a=ni(),b=ni(),k=ni();
				int g=gcd(a,b);
				int nd=2;
				if(g==a&&g==b)nd=0;
				else if(g==a||g==b) {nd=1;
					if(g==b) {
						a^=b;b^=a;a^=b;
					}
				}
				//k-=nd;
				//if(k<0) {ol("no");continue;}
				int totG=fact(g);
				int nda=diff(a,g);
				int ndb=diff(b,g);
				int totMoves=nda+ndb+2*totG;
				if(k<=totMoves&&k>=nd&&(k!=1||nd==1)){ol("yes");continue;}
				ol("no");
			}
			
		}
	private static int diff(int n, int g) {
			int idx=0,p=primes.get(0),tot=0;
			while(1l*p*p<=n) {
				int n1=0,n2=0;
				while(n%p==0) {
					n/=p;
					n1++;
				}
				while(g%p==0) {
					g/=p;
					n2++;
				}
				tot+=n1-n2;
				p=primes.get(++idx);
			}
			if(n!=g)tot++;
			return tot;
		}
	private static int fact(int n) {
			int idx=0,p=primes.get(0),tot=0;
			while(1l*p*p<=n) {
				while(n%p==0) {
					n/=p;tot++;
				}
				p=primes.get(++idx);
			}
			if(n!=1)tot++;
			return tot;
		}
	static void D() throws IOException {
		int t=ni();
		sieve(40000);
		while(t-->0) {
			int a=ni(),b=ni(),k=ni();
			int g=gcd(a,b);
			int nd=2;
			if(g==a&&a==b)nd=0;
			else if(g==a||g==b)nd=1;
			
			int idx=0,p=primes.get(0);
			int tot1=0,tot2=0,tot=0,gg=0;
			if(a==b&&k==1) {ol("NO");continue;}
			while(1l*p*p<=Math.max(a, b)) {
				int n1=0,n2=0;
				while(a%p==0) {
					a/=p;
					n1++;
				}
				while(b%p==0) {
					b/=p;
					n2++;
				}
				tot+=n1+n2;
				tot1+=Math.max(n1-n2, 0);
				tot2+=Math.max(n2-n1, 0);
				gg+=Math.min(n1, n2);
				p=primes.get(++idx);
			}
			if(a==b&&a!=1) {tot+=2;gg++;}
			if(a!=b) {
				if(a!=1) {tot++;tot1++;}
				if(b!=1) {tot++;tot2++;}
			}
			if(nd==0) {
				if(k%2==0&&tot>=k)ol("YES");
				else ol("NO");
			}else if(nd==1) {
				if(k%2==1)ol("YES");
				else {
					
				}
			}
//			idx=0;p=primes.get(0);
//			while(1l*p*p<=b) {
//				int n1=0;
//				while(b%p==0) {
//					b/=p;
//					n1++;
//				}
//				tot+=n1;
//				p=primes.get(++idx);
//			}
//			if(b!=1)tot++;
////			if(tot>1)
////				tot-=2;
//			out.println(tot>=k?"YES":"NO");
		}
		
	}
	static void E() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni();
			HashMap<String, Object[]>hm=new HashMap<String, Object[]>();
			long ans=0;
			String match="haha";
			while(n-->0) {
				String[]x=sc.nextLine().split(" ");
				//ol(x.length);
				if(x.length==3) {
					String cur=x[2];
					long subs=0l;
					if(cur.length()>=4&&cur.substring(0,4).equals(match))subs++;
					if(cur.length()>4&&cur.substring(1).equals(match))subs++;
					String pref=cur.substring(0,Math.min(cur.length(),3));
					String suff=cur.substring(Math.max(cur.length()-3, 0));
					
					Object[]v=new Object[] {subs,pref,suff};
					hm.put(x[0], v);
				}else {
					Object[]v1=hm.get(x[2]);
					Object[]v2=hm.get(x[4]);
					long val=(long)v1[0]+(long)v2[0];
					String pref1=(String)v1[1];
					String pref2=(String)v2[1];
					String suff1=(String)v1[2];
					String suff2=(String)v2[2];
					String con=suff1+pref2;
					for(int i=0;i+3<con.length();i++) {
						if(con.substring(i,i+4).equals(match))val++;
					}
					for(int i=0;i<pref2.length()&&pref1.length()<3;i++) {
						pref1+=pref2.charAt(i);
					}
					for(int i=suff1.length()-1;i>=0&&suff2.length()<3;i--) {
						suff2=suff1.charAt(i)+suff2;
					}
					hm.put(x[0], new Object[] {val,pref1,suff2});
				}
				if(n==0) {
					Object[]v=hm.get(x[0]);
					ans=(long)v[0];
				}
			}
			ol(""+ans);
		}
	}
	static void F() throws IOException {
		int t=ni();
		while(t-->0) {
			long a=nl(),b=nl();
			long ans=0;
			int lena=(int)Math.floor(Math.log10(a))+1;
			int lenb=(int)Math.floor(Math.log10(b))+1;
			long fc=10l;
			for(int i=0;i<lenb;i++,fc*=10l) {
				ans+=(b-a)/(fc/10);
				b-=b%fc;
				a-=a%fc;
			}
			ol(""+ans);
		}
	}
	static void F2() throws IOException {
		int n=ni(),t=ni(),k=ni();
		
	}
	static long [][]d1,d2,map;
	static long W;
	static int []dx=new int[] {0,1,-1,0};
	static int []dy=new int[] {1,0,0,-1};
	static void G() throws IOException {
		n=ni();
		m=ni();
		W=nl();
		map=nml(n,m);
		long oo=(long)1e18;
		d1=new long[n][m];d2=new long[n][m];
		bfs(0,0,d1);
		bfs(n-1,m-1,d2);
		ArrayList<int[]>ports=new ArrayList<int[]>();
		long bestP=oo;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j]>=1&&d1[i][j]!=-1) {
					bestP=Math.min(bestP,d1[i][j]*W+map[i][j]);
				}
			}
		}
		long ans=d1[n-1][m-1]*W;
		if(d1[n-1][m-1]==-1)ans=oo;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j]>=1&&d2[i][j]!=-1) {
				ans=Math.min(ans, bestP+d2[i][j]*W+map[i][j]);
				}
			}
		}
		
		out.println(ans>=oo?-1:ans);
	}
	private static void bfs(int i, int j,long[][]d) {
		d[i][j]=1;
		int[]q=new int[2*n*m];
		int e=0,s=0;
		q[e++]=i;q[e++]=j;
		while(s<e) {
			int x=q[s++],y=q[s++];
			for(int a=0;a<4;a++) {
				int nx=x+dx[a],ny=y+dy[a];
				if(nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==0&&map[nx][ny]!=-1) {
					q[e++]=nx;q[e++]=ny;
					d[nx][ny]=d[x][y]+1;
				}
			}
		}
		for(int a=0;a<d.length;a++)
			for(int b=0;b<d[0].length;b++)
				d[a][b]--;
		
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}
