452

#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <cstdio>

#define INF 10000000

using namespace std;

bool gr[26][26];
int daysreq[26],indegree[26];
int accumulated_days[26];
int t;

int bfs(queue<int> q)
{

	while(!q.empty())
	{
		int a = q.front();q.pop();
		for(int i=0;i<26;i++)
		{
			if(gr[a][i])
			{
				accumulated_days[i]=max(accumulated_days[i],accumulated_days[a]+daysreq[i]);
				if(--indegree[i]==0)
				q.push(i);
			}

		}

	}

	int MX = 0;
	for(int i=0;i<26;i++)
	{
		MX =  max(accumulated_days[i],MX);
	}
	cout<<MX<<"\n";
	if(t)
	cout<<"\n";

	return 0;
}

int main()
{
	string s;
	stringstream ss;
	getline(cin,s);
	ss<<s;
	ss>>t;
	getline(cin,s);
	ss.clear();
	while(t--)
	{
		for(int i=0;i<26;i++)
		{
			daysreq[i]=0;
			indegree[i]=0;
			accumulated_days[i]=0;
			for(int j=0;j<26;j++)
				gr[i][j]=0;
		}
		while(getline(cin,s) && s!="")
		{
			ss<<s;
			char c;
			int d,u;
			ss>>c>>d;
			u = c-'A';
			daysreq[u]=d;
			while(ss>>c)
			{
				gr[c-'A'][u]=1;
			}
			ss.clear();
		}

		for(int i=0;i<26;i++)
		{
			for(int j=0;j<26;j++)
			{
				if(gr[i][j])
					indegree[j]++;
			}
		}
		queue<int> q;
		for(int i=0;i<26;i++)
		{
			if(daysreq[i]!=0 && indegree[i]==0)
			{
				accumulated_days[i]=daysreq[i];
				q.push(i);
			}
		}
		bfs(q);
	}
	return 0;
}