8667: Painting Game

There is a paper strip divided into $n$ blank grids. For each $i(1\le i<n)$, grid i and i+1 are considered adjacent.

Alice and Bob are going to play a game on the strip. They take turns to make move. In one move the player must paint one of the remaining blank grids black, while keeping the rule that no two black grids are adjacent.

The game ends when one of the players is unable to paint any grid, and the score of the game is defined as the total number of grids painted black. Alice wants to minimize the score, while Bob wants to maximize it.

Given n and the side starting the game, find out the final score when both players play optimally.

The first line contains an integer T(1≤T≤105) - the number of test cases.

The first line of each test case contains an integer n(1≤n≤109) and a string $s(s\in \text{Alice},\text{Bob})$ - the number of grids and the starting player of this game.