题目背景

卡科福尼亚大陆每年都会举行歌曲大赛。每个参赛国家派出一名歌手或组合，观众可以给其他国家的节目投票，但不能给本国节目投票。

共有 $s$ 个参赛国家。每个国家最终会向排名前 $r$ 的节目授予分数：第一名获得 $r$ 分，第二名获得 $r-1$ 分，依此类推，第 $r$ 名获得 $1$ 分，其余节目不得分。一个国家在所有国家处获得的分数之和，就是它的最终得分。

音乐制作人 Dustin 想为某个指定国家制作节目，并通过调整节目内容，使该国获得尽可能高的总分。

题目描述

各国采用以下两种投票方式之一。

政治导向投票

政治导向国家按照首都之间的欧氏距离对其他国家排序：首都距离越近，节目排名越高。

对于任意一个国家，不会有两个其他国家的首都到它的首都距离相同。

质量导向投票

质量导向国家按照所有节目的客观艺术质量排名投票。每个国家的节目都有一个互不相同的质量名次，$1$ 表示质量最高，$s$ 表示质量最低。

修改节目

Dustin 可以把节目划分为恰好 $s-1$ 个部分。最初，所有部分都服务于表演者本国的原创内容；Dustin 可以把其中一些部分改为专门迎合其他国家。

修改产生以下影响：

• 若一个部分被用于迎合某个政治导向国家，则在该国的排名中，表演者国家上升一名；若已经排在第一名，则不再上升。上升时，原来位于上一名的国家下降一名。
• 对每个质量导向国家而言，每有一个部分不再服务于表演者本国的原创内容，表演者国家就在该国的排名中下降一名；若已经排在最后一名，则不再下降。

只有每个国家获得了多少个专门部分会影响结果，各部分在节目中的先后顺序无关紧要。

请计算 Dustin 进行最优修改后，指定国家能够得到的最大总分。

注意，任何国家都不能给自己的节目投票。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

1. 第一行包含一个整数 $s$（$1<s\le 100$），表示参赛国家数。
2. 接下来依次给出 $s$ 个国家的信息。每个国家占两行：
   • 第一行包含一个不含空格的国家名和一个字符：
     • q 表示该国采用质量导向投票；
     • p 表示该国采用政治导向投票。
   • 第二行包含三个整数 $x,y,rank$：
     • $(x,y)$ 是该国首都坐标，$-10000\le x,y\le 10000$；
     • $rank$ 是该国节目的艺术质量名次，取值为 $1$ 到 $s$，且同一测试用例中的所有名次互不相同。
3. 下一行包含一个整数 $r$（$0<r\le s-1$），表示每个国家会给排名前多少个其他国家授分。
4. 最后一行包含 Dustin 所负责国家的名称。

同一测试用例中的国家名称互不相同。

输出格式

对于每个测试用例，输出一行一个整数，表示指定国家能够获得的最大总分。

样例输入

2
3
Aulatrias q
0 0 1
Binen q
5 0 2
Cahin q
0 -4 3
2
Cahin
3
Aulatrias p
0 0 1
Binen p
5 0 2
Cahin p
0 -4 3
2
Binen

样例输出

2
4