题目描述

《狼人杀（The Werewolves）》是一款很受欢迎的卡牌游戏。
在某一局游戏中，共有 N 名玩家，编号为 1 到 N。每名玩家的真实身份只可能是以下两种之一：

• villager：村民
• werewolf：狼人

每名玩家都会发言一次。第 i 名玩家会说一句话，形式为：

• “玩家 x 是 villager”
• “玩家 x 是 werewolf”

已知规则如下：

1. 村民一定不会说谎；
2. 狼人可以说真话，也可以说假话。

我们只考虑所有满足上述规则的 合法身份分配方案。题目保证输入数据 至少存在一种合法方案。

现在需要将每个玩家分成以下三类：

1. 第 1 类：在所有合法方案中，该玩家都只能是村民；
2. 第 2 类：在所有合法方案中，该玩家都只能是狼人；
3. 第 3 类：在某些合法方案中是村民，在另一些合法方案中是狼人。

你需要输出：

• 第 1 类玩家的总人数；
• 第 2 类玩家的总人数。

补充说明

• 不会有玩家指认自己，即第 i 名玩家说的 x 一定满足 x ≠ i。

输入格式

第一行输入一个整数 T，表示测试数据组数。

对于每组测试数据：

• 第一行一个整数 N，表示玩家总数；
• 接下来 N 行，第 i 行包含一个整数 x 和一个字符串 S，表示第 i 名玩家声称：
  “玩家 x 的身份是 S”。

其中：

• S 只可能是 villager 或 werewolf。

输出格式

对于每组测试数据，输出一行两个整数：

第1类玩家数 第2类玩家数

两个整数之间用空格隔开。

输入输出样例

输入

1
2
2 werewolf
1 werewolf

输出

0 0

数据范围

• 1 <= T <= 10
• 1 <= N <= 10^5
• 1 <= x <= N
• x != i
• S ∈ {villager, werewolf}

题目保证每组数据至少存在一种合法身份分配方案。