Palindrome Game

Time limit2sMemory limit1024 MB

Summary

Cows take turns removing a positive palindrome number of stones from a pile of S (up to 10^(10^5)). Decide who wins with optimal play.

Level: Medium7 of 10
Topics: Game theory, Number theory, Dynamic programming
Solved: No attempts yet

Problem

Bessie and Elsie are playing a game with a pile of stones that initially contains $S$ stones ( $1\le S<10^{10^5}$ ). The two cows alternate turns, with Bessie going first. When it is a cow's turn, she must remove $x$ stones from the pile, where $x$ is any positive integer palindrome of the cow's choosing. If the pile is empty when a cow's turn starts, that cow loses.

Definition: A positive integer is a palindrome if it reads the same forward and backward. Examples of palindromes include 1, 121, and 9009. Leading zeros are not allowed, so 990 is not a palindrome.

There are $T$ ( $1\le T\le 10$ ) independent test cases. For each test case, print who wins the game if both cows play optimally.

Input

The first line contains $T$ , the number of test cases. The next $T$ lines describe the test cases, one line per test case.

Each test case is specified by a single integer $S$ .

Output

For each test case, output B if Bessie wins the game under optimal play starting with a pile of stones of size $S$ , or E otherwise, on a new line.

Examples1

Example 1
Input
```
3
8
10
12
```
Expected output
```
B
E
B
```