ABABAABA

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
You are given a uniformly randomly generated string S, consisting of letters from the set {"A", "B"}. Your task is to find a string T that appears in S as a subsequence exactly twice.
In other words, you need to find such a string T, that there exist exactly two sets of indexes i_{1}, i_{2}, ..., i_{T} and j_{1}, j_{2}, ..., j_{T} such that there exists some k, where i_{k} ≠ j_{k} and S_{{i1...iT}} = S_{{j1...jT}} = T.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string S.
The string S was generated randomly. For a generating string S, we first choose an integer N denoting a length of S. After that every symbol of the string S is chosen randomly from the set {"A", "B"} and the both symbols have equal probability to be chosen. Note that N is not choosen randomly.
Output
For each test case, output a string that occurs exactly twice as a subsequence in S, or output 1 if there is no such string. If there are more than one possible subsequences occurring exactly two times, you can print any one of them.
Constraints
 1 ≤ T ≤ 10
Subtasks
 Subtask #1 (10 points): 2 ≤ N ≤ 3
 Subtask #2 (26 points): 2 ≤ N ≤ 10
 Subtask #3 (64 points): 2 ≤ N ≤ 5000
Example
Input: 2 AAAA BAB Output: 1 B
Explanation
Test case #1:
 The string "AAAA" appears once as a subsequence in itself.
 The string "AAA" appears four times as a subsequence in "AAAA"; possible positions: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}.
 The strings "AA" and "A" also appear in "AAAA" as a subsequence strictly more than twice.
So, there is no string of "AAAA", which appears exactly twice. Hence answer is 1.
Test case #2: Two occurrences of "B" in "BAB" are {1} and {3} (1based indexing).
Author:  xcwgf666 
Tester:  zedthirtyeight 
Editorial  http://discuss.codechef.com/problems/ABABAABA 
Tags  adhoc, easymedium, ltime34, xcwgf666 
Date Added:  21022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions