베시와 엘시는 처음에 돌 \(S\)개가 들어 있는 돌무더기로 게임을 한다. (\(1\le S<10^{10^5}\)) 두 소는 번갈아 가며 차례를 진행하고, 베시가 먼저 시작한다. 자신의 차례가 되면 자신이 고른 양의 정수 팰린드롬 \(x\)만큼의 돌을 돌무더기에서 가져가야 한다. 자신의 차례가 시작될 때 돌무더기가 비어 있으면 그 소가 패배한다.

정의: 양의 정수를 앞에서부터 읽은 결과와 뒤에서부터 읽은 결과가 같으면 팰린드롬이라고 한다. 예를 들어 \(1\), \(121\), \(9009\)는 팰린드롬이다. 수의 앞에 0을 붙이는 것은 허용되지 않는다. 예를 들어 \(990\)은 팰린드롬이 아니다.

서로 독립적인 테스트 케이스가 \(T\)개 주어진다. (\(1\le T\le 10\)) 각 테스트 케이스에 대해 두 소가 모두 최적으로 플레이할 때 누가 승리하는지 출력하여라.

입력

첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.

다음 \(T\)개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 돌의 개수 \(S\)를 나타내는 하나의 정수로 이루어진다.

출력

각 테스트 케이스에 대해, 돌이 \(S\)개인 상태에서 시작하여 두 소가 모두 최적으로 플레이할 때 베시가 승리하면 B를 출력하고, 그렇지 않으면 E를 출력한다.

각 테스트 케이스의 답은 새로운 줄에 출력한다.

예제 입력

3
8
10
12

예제 출력

B
E
B

첫 번째 테스트 케이스에서 \(8\)은 팰린드롬이므로, 베시는 첫 번째 차례에 모든 돌을 가져가 승리를 보장할 수 있다.

두 번째 테스트 케이스에서 \(10\)은 팰린드롬이 아니므로, 베시는 첫 번째 차례에 모든 돌을 가져갈 수 없다. 베시가 첫 번째 차례에 몇 개의 돌을 가져가더라도 엘시는 두 번째 차례에 남은 돌을 모두 가져갈 수 있으므로 승리를 보장할 수 있다.

세 번째 테스트 케이스에서는 두 소가 모두 최적으로 플레이할 때 베시가 승리함을 증명할 수 있다.

서브태스크

출처

USACO 2024 February Contest, Bronze, Problem 1. Palindrome Game