가장 긴 감소 접미사

Sam은 외부 세계로 통하는 통신 경로를 하나 발견했습니다. 이 경로는 Clu가 열어 둔 것으로 보이지만, 실제로 작동하는지 확인하려면 올바른 비밀번호를 찾아야 합니다. Clu는 수많은 관문의 비밀번호를 모두 외우지 못해, 대개 관문 근처에 비밀번호를 적어 둡니다. 다만 비밀번호를 그대로 적지 않고, 벽에 적힌 여러 문자열 속에 부호화해 숨겨 둡니다. 비밀번호를 해독하는 첫 단계는, 벽에 적힌 각 문자열의 가장 긴 감소 접미사(LDS, Longest Decreasing Suffix) 를 찾는 것입니다. 그 다음 단계는 Sam이 알아서 처리할 수 있으니, 이 첫 단계만 도와주면 됩니다.

문자열의 감소 접미사란, 접미사 안의 각 문자가 바로 다음 문자보다 큰(엄격히 큰) 접미사를 말합니다. 문자열의 LDS는 그러한 접미사 중 가장 긴 것입니다. 예를 들어 문자열 abcdbca의 LDS는 ca이고, 문자열 abcdljksdflkjzfcba의 LDS는 zfcba입니다.

첫째 줄에 테스트 케이스의 개수($\le 50$)가 주어집니다. 그 다음 각 줄에 길이가 $< 100$인 입력 문자열이 하나씩 주어집니다. 입력 문자열은 소문자 a부터 z까지만으로 이루어져 있습니다.

각 테스트 케이스마다 입력 문자열의 가장 긴 감소 접미사를 찾아, 다음 형식으로 한 줄씩 출력합니다.

The longest decreasing suffix of <문자열> is <접미사>

여기서 <문자열>은 입력 문자열, <접미사>는 그 문자열의 LDS입니다.