Description

Archana is very fond of strings. She likes to solve many questions related to strings. She comes across a problem which she is unable to solve. Help her to solve. The problem is as follows: Given is a string of length L. Her task is to find the longest string from the given string with characters arranged in descending order of their ASCII code and in arithmetic progression. She wants the common difference should be as low as possible(at least 1) and the characters of the string to be of higher ASCII value.

Input

The first line of input contains an integer T denoting the number of test cases. Each test contains a string s of lengthL.

1<= T <= 100

3<= L <=1000

A<=s[i]<=Z

The string contains minimum three different characters.

Output

For each test case print the longest string.Case 1:Two strings of maximum length are possible- “CBA” and “RPQ”. But he wants the string to be of higher ASCII value therefore, the output is “RPQ”.Case 2:The String of maximum length is “JGDA”.

Sample Input 1

2
ABCPQR
ADGJPRT

Sample Output 1

RQP
JGDA

Code

package org.alphacat.third;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class DescendingOrder {

    private static final int ALPHABET_SIZE = 26;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < t; i++) {
            String s = scanner.nextLine();
            String res = problem(s);
            System.out.println(res);
        }

    }

    private static String problem(String s) {
        boolean[] charSet = getCharSet(s);
        int maxLen = 0;
        String maxString = "";
        for (int i = 0; i < charSet.length; i++) {

            if (!charSet[i]) {
                continue;
            }

            for (int step = 1; i + step < charSet.length; step++) {
                int len = 0;
                StringBuilder sb = new StringBuilder();
                for (int j = i; j < charSet.length; j += step) {
                    if (!charSet[j]) {
                        break;
                    }
                    ++len;
                    sb.insert(0, (char) (j + 'A'));
                }

                if (len > maxLen) {
                    maxLen = len;
                    maxString = sb.toString();
                } else if (len == maxLen && sb.charAt(0) > maxString.charAt(0)) {
                    maxString = sb.toString();
                }
            }

        }
        return maxString;
    }

    private static boolean[] getCharSet(String s) {
        boolean[] alphabet = new boolean[ALPHABET_SIZE];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            alphabet[c - 'A'] = true;
        }
        return alphabet;
    }
}