We start by defining a winning position and a losing position. If the current player wins given optimal play on both sides, the position is a winning position, otherwise the position is a losing position.

For positions that are not immediately winning or losing positions, we can make the following two observations:

- If one can make a move to a position that is a losing position, then the current position is a winning position.
- If one can only make moves to positions that are winning positions, then the current position is a losing position.

In the context of this problem, the pile having zero stones is a losing position, the pile having $1, 2, \dots, 9$ stones is a winning position, and the pile having ten stones is a losing position.

**Subtask 1: $S < 100$.**

We can naively check this process and compute for all $S$ in increasing order if they are winning positions or losing positions.

T = int(input()) def is_pal(j): s = str(j) return s == "".join(reversed(s)) for _ in range(T): S = int(input()) win = [False] * (S+1) for i in range(S+1): for j in range(1, i+1): if is_pal(j) and not win[i-j]: win[i] = True print("B" if win[S] else "E")

**Subtask 2: $S < 10^6$.**

This subtask rewarded people for experimenting with moves and only trying moves that involved taking at most $9$ stones.

T = int(input()) S = 10**6 win = [False] * (S+1) for i in range(S+1): for j in range(1, min(i+1, 10)): if not win[i-j]: win[i] = True for _ in range(T): S = int(input()) print("B" if win[S] else "E")

**Subtask 3: $S < 10^9$.**

If we look at the winning position and losing positions, we can see that a position is winning if and only if $S$ is not divisible by $10$. The proof of this follows directly from observing that taking anywhere from $1$ to $9$ stones is possible, but it is never possible to remove a multiple of ten. Therefore, we just naively check if the integer is divisible by $10$.

**Full Credit:**

To check if a very large integer is a multiple of $10$, it suffices to check if the last digit of the number is $0$.

Benjamin Qi's code:

T = int(input()) for _ in range(T): start = input() print('E' if start[-1] == '0' else 'B')