该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Farmer John 的农场中有 n 头牛。天天在农场中转来转去，牛们觉得很闷，它们纷纷要求 John 带它们出去旅行。

为了防止牛们在旅途中发生“暧昧”，John 准备挑选一些牛。John 希望他挑选出的牛中的任意两头牛至少满足以下四个条件之一：

1、身高差超过 d，巨大的身高差会使得它们互相望而却步；

2、要么都是公牛，要么都是母牛，这样它们就没法暧昧了；

3、具有不同的发型，这样它们会互相看不顺眼；

4、穿的衣服类型相同，这样它们会因撞衫而尴尬。

为了尽量安抚牛们，John 希望能带尽可能多的牛出去旅行。

他最多能带多少头牛出去呢？

Input

第一行：包含一个整数 T，表示数据组数

接下来 T 组数据，每组数据：

• 第一行：包含两个整数 n, d
• 接下来 n 行，每行描述一头奶牛，包括四部分：首先是一个整数 Hi，用来表示身高；接着是一个字符 Si，用来表示性别；然后是一个字符串 Fi，用来表示发型；最后是一个字符串 Di，用来表示衣服类型。

Output

T 行，每组数据的答案占一行

Sample Input

2
2 10
20 M bar skii
30 F bar socc
4 50
35 M glass pro
0 M bar skii
43 M bar chess
30 F bar socc

Sample Output

1
3

Data Size

100% 的数据：1 ≤ T ≤ 100, 1 ≤ n ≤ 500, 10 ≤ d ≤ 50, 0 ≤ Hi ≤ 5000, Si ∈ {M, F}, |Fi|, |Di| ≤ 100