Combo

You are playing an action video game. The game controller has buttons, A, B, X, and Y. In this game, you can get coins with combo moves. You can make a combo move by pressing buttons in sequence.

This game has a secret sequence of buttons, which can be represented as a string S of those characters. You don't know the string S, but you know its length N.

You also know that the first character of S never reappears in it. For example, S can be "ABXYY" or "XYYAA", but cannot be "AAAAA" or "BXYBX".

You can press a sequence of up to 4N buttons for a combo move. Let p be the string which represents the sequence of the buttons you pressed. The number of coins you get for this move is calculated as the length of the longest prefix of S which is also a substring of p. A substring of a string t is a contiguous (possibly empty) sequence of characters within t. A prefix of t is a substring of that is empty or contains the first character of t.

For example, if S is "ABXYY" and p is "XXYYABYABXAY", you will get 3 coins because "ABX" is the longest prefix of S that is also a substring of p.

Your task is to determine the secret string S using few combo moves.

• 1 ≤ N ≤ 2 000
• Each character of the string S is A, B, X, or Y.
• The first character of S never reappears in S.

Note that your score for each subtask is the minimum of the scores for the test cases in the subtask.