400913: GYM100283 G Jenga In The Military Unit

After Bakkar finished the 45 days at the training center. He was assigned to the Air Defense Unit to complete his service period there. His day at the unit is very routine; he wakes up at 6 am to attend the morning line he starts exercising for about an hour. He has a daily guarding shift that lasts for 3 hours and varies from day to day in its timing. Then he starts to do some office work for the Major-General.

The day usually ends at 6 pm where he and the other soldiers rest for about 2 to 3 hours then they go to sleep. They usually take a shower, eat and then stay for a while talking or doing any boring stuff until they fall a sleep tired.

One day Bakkar and the other soldiers didn't have much to do on their day since most of the officers were not present at the unit. The day ended and they had some energy left. They were really bored and wanted to do something interesting so they decided to play some games but didn’t know what to play. On his last vacation Bakkar saw an interesting game on Wikipedia called Jenga. He also played a couple of games with Hassona. He also had a picture of the game with him.

He started explaining the game to the other soldiers; Jenga is a two player game that starts with a tower of height N with 3 blocks on each level and the two players alternate turns. Consecutive levels have blocks perpendicular on each other. Each turn the player has to remove a block from a level that is fully covered from the top (i.e he can neither remove a block from the top most level nor from the level below it if the top most level is not yet full). Then he places the removed block in the top most level if it contains < 3 blocks, otherwise he creates a new level on the top of the tower using this block (making it perpendicular on the previous level as well). Newly added levels are treated like original levels, so players can take blocks from them while satisfying the mentioned restrictions. For the tower to maintain its balance every level must satisfy at least one of the following conditions:

1) The middle block exists in the level

2) The 2 side (outer) blocks exist in the level

Otherwise, the whole tower collapse. The players keep playing as long as there is a valid moves that won't make the tower collapse. The player who is not able to make a move loses the game.

The image above that Bakkar has, shows how the tower can look like in the middle of a game.

Bakkar and Wahdan will play against each other and they will use tower of height N, Bakkar will play first and both play optimally. Can you find out who is going to win?

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  10⁴). Followed by T test cases, each test case will be a single integer N, the height of the tower (2  ≤  N  ≤  10⁹).

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then the name of the player who will win, either Bakkar or Wahdan.

3
2
12
100

Case 1: Bakkar
Case 2: Wahdan
Case 3: Bakkar