一位母亲希望在她的孩子们之间分享一块巧克力。孩子可以是男孩或女孩。孩子们围成一圈，按顺时针方向依次拿取一行巧克力。起初，巧克力块有 $n$ 行和 $m$ 列。每个男孩都很贪婪，会从巧克力块较长的一边拿走一行。每个女孩为了保持身材，会从较短的一边拿走一行。母亲必须选择从哪个孩子开始，以使分享到巧克力的孩子数量最大化。
输入格式
输入的第一行包含一个整数 $z$，表示测试用例的数量。接下来是各测试用例的描述。 每个测试用例包含两个由空格分隔的整数 $n$ 和 $m$ ($1 \le n, m \le 10^6$)。随后是一个空格，以及一个由字母 “B” 和 “G” 组成的序列，按顺时针顺序标识圆圈上的孩子。序列的长度不超过 $10^6$。
输出格式
对于每个测试用例，输出一行，包含一个整数：能够吃到巧克力的孩子的最大数量。即使同一个孩子拿到了两次巧克力，也不要重复计数。
样例
样例输入 1
3 4 4 GGGGGGG 4 4 BBBBBBB 4 4 GBGBBBG
样例输出 1
7 4 7