1020 - A Childhood Game

Both Alice and Bob know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble looses the game. If Bob starts first, then the player who takes the last marble wins the game.Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.

Now you are given the initial number of marbles and the name of the player who starts first. Then you have to find the winner of the game if both of them play optimally.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n < 2³¹) and the name of the player who starts first.

Output

For each case, print the case number and the name of the winning player.

题目类型：Bash博弈变形

算法分析：当Bob先手时，本题可以看做是Bash博弈问题，因为求解谁拿走最后一个石头和求解留给对方没法选石子的状态这两个问题是等价的。而当Alice先手时，由于谁拿走最后一个石子会输，所以初始时石子的个数%3 == 1的话，那个先手的人就会输，这可由Bash博弈推得

« 上一篇：lightoj1019

lightoj1029：下一篇 »