Find Distinct Palindromic Substrings

Given a string 'S', identify and print all distinct palindromic substrings within it. A palindrome reads the same forwards and backwards. For example, 'bccb' is a palindrome, whereas 'def' is not.

Input:

The first line of input contains an integer ‘T’, indicating the number of test cases. Each following test case contains a single string 'S'.

Output:

For each test case, output all distinct palindromic substrings of the provided string. These substrings must be sorted and space-separated. Print each test case result on a new line.

Example:

Input:

T = 1 S = "abac"

Output:

a aba b c

Constraints:

• 1 <= T <= 10
• 1 <= |S| <= 1000
• String S is composed of lowercase English letters only.
• Time limit: 1 sec