Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXL 300010

char s[MAXL];

int val[20010],pos[20010];

namespace AC

{

	struct node

	{

		int tr[26],fail,fa;

	}t[MAXL];

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int root;

	inline void insert(char s[],int id)

	{

		register int l = strlen(s);

		register int cur = root;

		for(register int i = 0;i < l;++i)

		{

			register int w = s[i] - 'a';

			if(t[cur].tr[w] == 0)t[t[cur].tr[w] = newnode()].fa = cur;

			cur = t[cur].tr[w];

		}

		pos[id] = cur;

		return;

	}

	inline void makefail()

	{

		register queue<int> q;

		for(register int i = 0;i < 26;++i)

		{

			if(t[root].tr[i])

			{

				t[t[root].tr[i]].fail = root;

				q.push(t[root].tr[i]);

			}

		}

		while(!q.empty())

		{

			register int k = q.front();q.pop();

			for(register int i = 0;i < 26;++i)

			{

				if(t[k].tr[i])

				{

					t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

					q.push(t[k].tr[i]);

				}

				else

				{

					t[k].tr[i] = t[t[k].fail].tr[i];

				}

			}

		}

		return;

	}

	int rnk[MAXL],siz[MAXL],tot = 0;

	struct edge

	{

		int to,nxt;

	}e[MAXL];

	int edgenum = 0;

	int lin[MAXL] = {0};

	inline void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	inline void dfs(int k)

	{

		siz[k] = 1;

		rnk[k] = ++tot;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			dfs(e[i].to);

			siz[k] += siz[e[i].to];

		}

		return;

	}

}

namespace SEG

{

	struct node

	{

		int lc,rc;

		int tag;

	}t[MAXL << 1];

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	inline void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	inline void pushdown(int rt)

	{

		t[t[rt].lc].tag = max(t[t[rt].lc].tag,t[rt].tag);

		t[t[rt].rc].tag = max(t[t[rt].rc].tag,t[rt].tag);

		return;

	}

	inline void add(int rt,int L,int R,int k,int l,int r)

	{

		if(k <= t[rt].tag)return;

		if(L <= l && r <= R){t[rt].tag = k;return;}

		pushdown(rt);

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

		return;

	}

	inline void add(int p,int v)

	{

		add(root,AC::rnk[p],AC::rnk[p] + AC::siz[p] - 1,v,1,AC::ptr + 1);

		return;

	}

	inline int query(int rt,int p,int l,int r)

	{

		if(l == r)return t[rt].tag;

		pushdown(rt);

		if(p <= mid)return query(t[rt].lc,p,l,mid);

		else return query(t[rt].rc,p,mid + 1,r);

	}

	inline int query(int p)

	{

		return query(root,AC::rnk[p],1,AC::ptr + 1);

	}

}

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

void work()

{

	AC::ptr = 0;

	memset(AC::t,0,sizeof(AC::t));

	SEG::ptr = 0;

	memset(SEG::t,0,sizeof(SEG::t));

	AC::tot = 0;

	AC::edgenum = 0;

	memset(AC::lin,0,sizeof(AC::lin));

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)

	{

		scanf("%s",s);

		val[i] = rd();

		AC::insert(s,i);

	}

	SEG::build(SEG::root,1,AC::ptr + 1);

	AC::makefail();

	for(register int i = 1;i <= AC::ptr;++i)AC::add(AC::t[i].fail,i);

	AC::dfs(AC::root);

	int ans = 0;

	for(register int k = 1;k <= n;++k)

	{

		register int v = -0x3f3f3f3f;

		register int cur = pos[k];

		for(;cur;cur = AC::t[cur].fa)

		{

			v = max(v,SEG::query(cur));

		}

		SEG::add(pos[k],v + val[k]);

		ans = max(ans,v + val[k]);

	}//cout << "##" << endl;

	cout << ans << endl;

	return;

}

int main()

{

	freopen("Data_P2963.in","r",stdin);

	freopen("Data_P2963.out","w",stdout);

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}