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.
#include<bits/stdc++.h>
//#include<unordered_map>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<sstream>
using namespace std;
#define int long long
#define ull unsigned long long
//#define ll long long
#define db double
#define str string
//#define ac() cout<<"Yes"<<endl
//#define wa()  cout<<"No"<<endl
void ac(int x){if(x)puts("YES");else puts("NO");}
#define ddd cout<<"---debug---"<<endl;
#define ff(a,b) for(signed long long (a)=1;(a)<=(b);(a)++)
#define fff(a,b) for(signed long long (a)=0;(a)<(b);(a)++)
#define rff(a,b) for(signed long long (a)=(b);(a)>=1;(a)--)
#define rfff(a,b) for(signed long long (a)=(b)-1;(a)>=0;(a)--)
#define re readdd()
#define pr(a) printtt(a)
#define pee puts("");
#define eee putchar(' ');
#define pss(a) push_back(a)
#define ps(a) push(a)
#define SZ(x) ((int)x.size())
#define epp empty()
#define all(x) x.begin(),x.end()
#define asd signed QP;scanf("%d",&QP);while(QP--)
#define alll(x,y) x+1,x+1+y
#define SL(x) strlen(x)
#define SC(x) scanf("%s",x)
#define CL(x) (x).clear()
typedef pair<int,int> PI;
typedef vector<int> VE;
#define VEP vector<pair<int,int> >
#define fir first
#define sec second
#define ist insert
#define PP(x) (x.pop())
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//
int ppow(int a,int b,int mod){a%=mod;//
int ans=1%mod;while(b){if(b&1)ans=(long long)ans*a%mod;
a=(long long)a*a%mod;b>>=1;}return ans;}
int readdd(){int x=0,f=1;char c=getchar();//
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return f*x;}
void printtt(int x){if(x<0)putchar('-'),x=-x;
if(x>=10)printtt(x/10);putchar(x%10+'0');}
bool addd(int a,int b){return a>b;}
int lowbit(int x){return x&-x;}
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
//bit
const int BN=2e6+5;
struct BIT{
    int c[BN];
    void init(){memset(c,0,sizeof c);}
    int lowbit(int i){return i&-i;}
    void add(int i,int t){while(i<BN)c[i]+=t,i+=lowbit(i);}
    int ask(int i){int ans=0;while(i)ans+=c[i],i-=lowbit(i);return ans;}
};
//
bool Isprime(int x){
    for(int i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
bool isdigit(char c){
    return c>='0'&&c<='9';
}
//dsu
const int FN=2e6+5;
int pre[FN];
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
//
const int SGTN=2e6+5;
struct SGT{
    int a[SGTN<<2];
    int la[SGTN<<2];
    void pd(int x){
        if(la[x]){
            a[x*2]+=la[x],a[x*2+1]+=la[x];
            la[x*2]+=la[x],la[x*2+1]+=la[x];
            la[x]=0;
        }
    }
//    void pd(int x,int l,int r){
//        if(la[x]){
//            int mid=(l+r)/2;
//            a[x*2]+=la[x]*(mid-l+1),a[x*2+1]+=la[x]*(r-mid);
//            la[x*2]+=la[x],la[x*2+1]+=la[x];
//            la[x]=0;
//        }
//    }
    void pp(int x){
        a[x]=max(a[x*2],a[x*2+1]);
    }
    void add(int st,int ed,int val,int l,int r,int x){//区间加法
        if(st<=l&&ed>=r){
            a[x]+=val;
            la[x]+=val;
            return ;
        }
        pd(x);
        int mid=(l+r)/2;
        if(st<=mid)add(st,ed,val,l,mid,x*2);
        if(ed>mid)add(st,ed,val,mid+1,r,x*2+1);
        pp(x);
    }
    int ask(int p,int l,int r,int x){//单点查询
        if(l==r)return a[x];
        pd(x);
        int mid=(l+r)/2;
        if(p<=mid)return ask(p,l,mid,x*2);
        else return ask(p,mid+1,r,x*2+1);
    }
    void update(int p,int val,int l,int r,int x){//单点修改
        if(l==r){
            a[x]=val;return ;
        }
        pd(x);
        int mid=(l+r)/2;
        if(p<=mid)update(p,val,l,mid,x*2);
        else update(p,val,mid+1,r,x*2+1);
        pp(x);
    }
    void build(int l,int r,int x){
        a[x]=-1e9;la[x]=0;
        if(l==r)return ;
        int mid=(l+r)/2;
        build(l,mid,x*2);build(mid+1,r,x*2+1);
    }
};
//
const double Pi=acos(-1);
const double eps=1e-7;
//const int mod=1e9+7;
const int mod=998244353;
const int modd=mod-1;
//
//const int maxm=2e6+5;
const int maxm=2e6+5;
//int a[maxm];
//int b[maxm];
//int c[maxm];
char s[maxm];
char t[maxm];
VE g[maxm];
VE gg[maxm];
int n,m,q,k;
//

struct Node{
    string l,r;
    int cnt;
};
Node f1(string s){
    Node t={"","",0};
    int n=s.size();
    for(int i=3;i<n;i++){
        if(s[i-3]=='h'&&s[i-2]=='a'&&s[i-1]=='h'&&s[i]=='a'){
            t.cnt++;
        }
    }
    for(auto i:s){
        t.l+=i;
        if(t.l.size()>=3)break;
    }
    for(int i=max(0LL,(n-1)-3+1);i<n;i++){
        t.r+=s[i];
    }
    return t;
}
Node f2(Node x,Node y){
    Node t={"","",0};
    t.cnt+=x.cnt+y.cnt;
    t.l=x.l;
    t.r=y.r;
    if(t.l.size()<3){
        for(auto i:y.l){
            t.l+=i;
            if(t.l.size()>=3)break;
        }
    }
    if(t.r.size()<3){
            auto it=x.r.rbegin();
            while(it!=x.r.rend()){
                t.r=*it+t.r;
                if(t.r.size()>=3)break;
            }
    }
    string s=x.r+y.l;
    int n=s.size();
    for(int i=3;i<n;i++){
        if(s[i-3]=='h'&&s[i-2]=='a'&&s[i-1]=='h'&&s[i]=='a'){
            t.cnt++;
        }
    }
    return t;
}
void solve(){
    cin>>n;getchar();
    map<string,Node>mp;
    string last;
    ff(i,n){
        string s;
        getline(cin,s);
        int f=0;
        for(auto i:s){
            if(i==':')f=1;
        }
        if(f==1){//变量定义
            string name,val;
            int p=0;
            for(auto i:s){
                if(i==' ')continue;
                if(i=='=')continue;
                if(i==':'){
                    p=1;continue;
                }
                if(p==0)name+=i;
                else val+=i;
            }
            Node t=f1(val);
            mp[name]=t;
            last=name;
//            cout<<name<<' '<<val<<endl;
//            cout<<t.l<<' '<<t.r<<' '<<t.cnt<<endl;
        }else{//加法
            string name,v1,v2;
            int p=0;
            for(auto i:s){
                if(i==' ')continue;
                if(i=='='){
                    p=1;continue;
                }
                if(i=='+'){
                    p=2;continue;
                }
                if(p==0){
                    name+=i;
                }else if(p==1){
                    v1+=i;
                }else if(p==2){
                    v2+=i;
                }
            }
            Node t=f2(mp[v1],mp[v2]);
            mp[name]=t;
            last=name;
//            cout<<name<<' '<<v1<<' '<<v2<<endl;
//            cout<<t.l<<' '<<t.r<<' '<<t.cnt<<endl;
        }
    }
    cout<<mp[last].cnt<<endl;
}
void init(){



}
signed main(){
    init();
//    while(1)
//    asd
    int T;cin>>T;while(T--)
        solve();
    return 0;
}
/*

*/
