278 - Chess

著名的八皇后問題是把八個皇后放在一個8x8的棋盤上，並使得彼此之間不能互相攻擊。現在，我們想知道如何在一個 m x n 的棋盤上放置最多數量的單一棋種(城堡Rook，騎士Knight，皇后Queen，國王King，其中一種)，使得彼此之間不能互相攻擊。

INPUT

輸入的第一列有一個整數，表示有幾組測試資料。接下來的每列一開始會給定棋種的名稱，r k Q K，依序分別表示城堡Rook，騎士Knight，皇后Queen，國王King。接著會有兩個整數 m (4<=m<=10)，n (4<=n<=10)，表示棋盤的列數與行數。

Output

針對每組測試資料，你必須輸出棋盤上可放置最大數量的棋子，使得彼此之間不會互相攻擊。
注意：棋盤的左下角坐標為1, 1。

SAMPLE INPUT

2
r 6 7
k 8 8

SAMPLE OUTPUT

6
32