B. Who's Opposite?

 Prepbuddy has a string

$S$ consisting of lowercase Latin Letters. The String $S$ can contain some repeated characters, no repeated characters, and maybe all repeated characters. He is trying to find the first character which is non-repeating in $S$. The String $S$ contains many non-repeating characters, so he is not able to find the answer. You can help him to find the answer.

Note:- Print $-1$ if there is no non-repeating character.

Input Format

The first line contains $T$ denoting the number of test cases. Then following each test case, the next line contains the string $S$.

#Solution in C++4

#include <iostream> #include <unordered_map> using namespace std; int nonRepeatingChar(string str, int n) { unordered_map<char, pair<int, int>> map; for(int i = 0 ; i < n; i++) { map[str[i]].first++; map[str[i]].second = i; } // stores index of first non-repeating character int min_index = n; // traverse map and find character having count 1 and // having minimum index in the string for (auto it : map) { int count = it.second.first; int firstIndex = it.second.second; if (count == 1 && firstIndex < min_index) min_index = firstIndex; } return min_index; } int main() { int t; cin>>t; while(t--){ string s; cin>>s; int n = s.length(); int index = nonRepeatingChar(s, n); if (index != n) cout<<index<<endl; else cout<<-1<<endl; } return 0; }

Output Format

For each test case, print the index of the first non-repeating character present in the string. Print $-1$ if there is no non-repeating character.

Constraint

$1<=T<=900$ $1<=|S|<={10}^4$, where $|S|$ denotes the length of string $S$.

Time Limit

1 second

Example

Input

3
hello zxvczbtxyzvy xxyyzz

Output

0 3 -1

Sample test case Explanation

In the first test case. 'h', 'e', and 'o' are non-repeating characters, but the character 'h' is the first non-repeating. So the answer is the index of 'h'. Output: 0

In the second test case 'z' is present at the index 0,4 and 9 'x' is present at the index 1 and 7 'v' is present at the index 2 and 10 'c' is present only at index 3, so 3 is the output. 'b' is present only at index 5, so 5 is the output 't' is present only at index 6, so 6 is the output

'c', 'b', and 't' are non-repeating characters, but the character 'c' is the first non-repeating. that's why 'c' is the answer.

Output: 3