First Non-Repeating Character

You are given a string and your task is to find the first non-repeating character in it. If all characters in the string are repeating (ignoring spaces), then output "None". The solution should process multiple test cases.

For each test case, the input consists of a single line containing the string. The answer should be computed in O(n) time where n is the length of the string.

Note: Spaces are ignored when determining whether a character is repeating.

Example: For the string hello world, the first non-repeating character is h; for programming, it is p; and for aabbcc, the answer is None.

Mathematically, if we define the frequency function \( f(c) \) for each character \( c \) in string \( s \), then we are looking for the smallest index \( i \) such that \( s_i \neq ' ' \) and \( f(s_i)=1 \). In LaTeX: $$\min\{i \mid s_i \neq ' ' \text{ and } f(s_i)=1\}.$$

inputFormat

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a string \( s \) for which you have to determine the first non-repeating character.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the first non-repeating character. If there is no such character, output "None".

All output should be written to standard output (stdout), each result on a new line.

## sample

3
hello world
programming
aabbcc

h
p
None

</p>