A Math Magic game consists of a number of equal-sized blocks. Each block in Math Magic is divided into 4 triangles where each triangle takes a color from Blue (B), Green (G), Red (R), or Yellow (Y) and an integer from 0 to 9.
Starting with the center block, at each step a player can adjoin a new block in one of four directions along the horizontal or vertical axes centered at the center block. The new block is attached to an existing block in such a way that the two corresponding adjoined triangles must have the same color. The score of each block is calculated based on the color of the adjoined triangle, the integer in the adjoined triangle of the new block and the sum of four integers in the new block as follows:
If a block cannot be added in the board or the player does not wish to include in the board, then its score is –S and the block is skipped. Notice that the center block, i.e. the first block, does not have a score. For example, consider the following steps to add a new block and their corresponding scores
S = 4 + 4 + 0 + 1 = 9
x = 4
Color of the adjoined triangle: red
Score = S * x = 9 * 4 = 36
S = 1 + 3 = 4
x = 3
Color of the adjoined triangle: yellow
Score = 4
Given a list of blocks, a player will use the first one as the center block and either add or skip the remaining blocks to the board one at a time in sequence. The blocks can be rotated before being added to the board but they must be considered in the same order as given. Your task is to find the maximum total score a player could get.
The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 40. The following lines describe the datasets.
The first line of each dataset contains an integer n(n≤250, 000), which is the total number of blocks including the center block as the first one. For the next n lines, each line contains 8 characters representing the colors and integers for the block’s triangle in clockwise order: c1n1c2n2c3n3c4n4 where ci (ci takes values from Y, R, G, or B standing for yellow, red, green or blue respectively), ni (ni takes an integer value from 0 to 9) is the color and integer of the i triangle respectively (1 ≤ i ≤ 4).
For each dataset, write on one line the maximum point score a player could get.
## Input
The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 40. The following lines describe the datasets.The first line of each dataset contains an integer n(n≤250, 000), which is the total number of blocks including the center block as the first one. For the next n lines, each line contains 8 characters representing the colors and integers for the block’s triangle in clockwise order: c1n1c2n2c3n3c4n4 where ci (ci takes values from Y, R, G, or B standing for yellow, red, green or blue respectively), ni (ni takes an integer value from 0 to 9) is the color and integer of the i triangle respectively (1 ≤ i ≤ 4).
## Output
For each dataset, write on one line the maximum point score a player could get.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of blocks, with $ n \leq 250{,}000 $.
Let $ B = (b_0, b_1, \dots, b_{n-1}) $ be the sequence of blocks, where each block $ b_i = (c_{i,1}, v_{i,1}, c_{i,2}, v_{i,2}, c_{i,3}, v_{i,3}, c_{i,4}, v_{i,4}) $, with $ c_{i,j} \in \{Y, R, G, B\} $, $ v_{i,j} \in \{0,1,\dots,9\} $, representing the color and integer of the $ j $-th triangle in clockwise order.
Let $ S(b_i) = \sum_{j=1}^4 v_{i,j} $ be the sum of integers in block $ b_i $.
A block $ b_k $ (for $ k \geq 1 $) can be placed adjacent to an existing block if, after any rotation (0°, 90°, 180°, or 270°), one of its four triangles matches in color with the corresponding adjacent triangle of a neighboring block.
**Constraints**
1. The first block $ b_0 $ is fixed as the center block and contributes no score.
2. For each subsequent block $ b_k $ ($ k \geq 1 $), the player may either:
- **Skip** it, contributing score $ -S(b_k) $, or
- **Place** it adjacent to the existing structure, matching exactly one of its four triangles to an exposed triangle of the current board, contributing score $ S(b_k) \cdot x $, where $ x $ is the integer value of the matching triangle in $ b_k $.
3. Blocks must be processed in order $ b_1, b_2, \dots, b_{n-1} $.
4. Rotation is allowed: for each block, any of the 4 cyclic shifts of its triangle sequence is permissible.
**Objective**
Maximize the total score over all choices of placement or skip for blocks $ b_1 $ to $ b_{n-1} $, under the adjacency color-matching constraint.
Let $ \mathcal{D} $ be the set of all possible exposed edge colors (color, position) on the current board.
At each step $ k $, for each possible rotation $ r \in \{0,1,2,3\} $, define the rotated block $ b_k^{(r)} = (c_{i,(j+r)\bmod 4}, v_{i,(j+r)\bmod 4})_{j=1}^4 $.
For each exposed edge color $ \text{col} \in \mathcal{D} $, if $ b_k^{(r)} $ has a triangle with color $ \text{col} $ at some position $ j $, then placing $ b_k^{(r)} $ adjacent to that edge yields score $ S(b_k) \cdot v_{k,(j+r)\bmod 4} $, and updates $ \mathcal{D} $ by adding the three new exposed edges of $ b_k^{(r)} $.
**Goal:**
Compute the maximum total score achievable over all valid sequences of placements and skips.