#PU1395. USACO 2024 February Contest, Bronze — Problem 1. Palindrome Game

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

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

题目描述

Bessie and Elsie are playing a game with a pile of stones that initially contains SS stones (1≤S<101051\le S<10^{10^5}). The two cows alternate turns, with Bessie going first. When it is a cow's turn, she must remove xx stones from the pile, where xx 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; e.g., 990 is not a palindrome. There are TT (1≤T≤101\le T\le 10) independent test cases. For each test case, print who wins the game if both cows play optimally.

输入格式

The first line contains TT, the number of test cases. The next TT lines describe the test cases, one line per test case. Each test case is specified by a single integer SS.

输出格式

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

数据范围

Inputs 2-4: S<100S<100 Inputs 5-7: S<106S<10^6 Inputs 8-10: S<109S<10^9 Inputs 11-13: No additional constraints. Problem credits: Nick Wu

样例

样例 1

3
8
10
12
B
E
B
For the first test case, Bessie can remove all the stones on her first move,
since $8$ is a palindrome, guaranteeing her win.
For the second test case, $10$ is not a palindrome, so Bessie cannot remove all
the stones on her first move. Regardless of how many stones  Bessie removes on
her first move, Elsie can always remove all remaining stones on her second move,
guaranteeing her win.
For the third test case, it can be proven that Bessie wins under optimal play.