First Non-Repeating Character

Given a string s, determine its first non-repeating character. If every character in the string appears more than once, output "-1". This problem tests your ability to count character frequencies and efficiently identify the unique character that occurs first.

Formally, for a string \( s \) consisting of characters, find the smallest index \( i \) such that the frequency of \( s_i \) in \( s \) is exactly one. If no such character exists, return \( -1 \).

inputFormat

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a non-empty string \( s \).

All input should be read from standard input.

outputFormat

For each test case, output a single line containing the first non-repeating character of the corresponding string. If every character repeats, output "-1".

All output should be written to standard output.

4
aabbccddeeffg
aabbcc
abcd
aabbcdc

g
-1
a
d