팰린드롬 게임

시간 제한2초메모리 제한1024 MB

요약

돌 S개가 쌓인 더미에서 두 소가 번갈아 팔린드롬 수만큼 돌을 가져갑니다. 돌이 없는 상태에서 차례가 된 소가 집니다. 최적으로 둘 때 누가 이기는지 구합니다.

난이도: 보통10점 중 7점
유형: 게임 이론, 정수론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Bessie와 Elsie는 처음에 돌멩이가 $S$ 개( $1\le S<10^{10^5}$ ) 든 더미로 게임을 한다. 두 소는 번갈아 차례를 가지며, 첫 차례는 Bessie에게 있다. 차례가 된 소는 자신이 고른 양의 정수 팰린드롬 $x$ 를 골라 더미에서 돌멩이 $x$ 개를 제거해야 한다. 차례를 시작할 때 더미가 비어 있으면 그 소가 진다.

정의: 양의 정수가 앞에서 읽으나 뒤에서 읽으나 같으면 팰린드롬이다. 팰린드롬의 예로 1, 121, 9009가 있다. 앞자리에 0을 둘 수 없으므로 990은 팰린드롬이 아니다.

테스트 케이스는 $T$ 개( $1\le T\le 10$ )이며, 각 테스트 케이스는 서로 독립이다. 각 테스트 케이스마다 두 소가 최적으로 플레이할 때 누가 이기는지 출력한다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 줄에는 한 줄에 테스트 케이스 하나씩 주어진다.

각 테스트 케이스는 정수 $S$ 하나로 주어진다.

출력

각 테스트 케이스마다 돌멩이가 $S$ 개인 더미에서 최적으로 플레이할 때 Bessie가 이기면 B를, 그렇지 않으면 E를 새 줄에 출력한다.

예제1

예제 1
입력
```
3
8
10
12
```
예상 출력
```
B
E
B
```