有一条纸带被分成了 $n$ 个空白格子。对于每个 $i(1 \le i < n)$，格子 $i$ 和 $i + 1$ 被视为相邻。

Alice 和 Bob 将在这条纸带上进行游戏。他们轮流进行操作。在一次操作中，玩家必须将剩余的空白格子中的一个涂成黑色，同时必须遵守“不能有两个黑色格子相邻”的规则。

当其中一名玩家无法再涂任何格子时，游戏结束。游戏的得分定义为被涂成黑色的格子总数。Alice 希望最小化得分，而 Bob 希望最大化得分。

给定 $n$ 和先手玩家，求双方都采取最优策略时的最终得分。

输入格式

第一行包含一个整数 $T(1 \le T \le 10^5)$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n(1 \le n \le 10^9)$ 和一个字符串 $s(s \in \{\text{Alice}, \text{Bob}\})$，分别表示格子的数量和游戏的先手玩家。

输出格式

对于每个测试用例，输出双方都采取最优策略时的最终得分，每个结果占一行。

样例

输入 1

4
3 Alice
3 Bob
19 Alice
23 Bob

输出 1

1
2
8
10