Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. Binary to Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$b$$$ of length $$$n$$$.

Construct a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters such that for each $$$i$$$ ($$$1 \le i \le n$$$):

  • if $$$b_i = 1$$$, then every substring$$$^{\text{∗}}$$$ of $$$s$$$ of length $$$i$$$ is a palindrome$$$^{\text{†}}$$$;
  • if $$$b_i = 0$$$, then at least one substring of $$$s$$$ of length $$$i$$$ is not a palindrome.

Print the lexicographically smallest$$$^{\text{‡}}$$$ such string $$$s$$$. If no such string exists, print $$$-1$$$.

$$$^{\text{∗}}$$$A string $$$x$$$ is a substring of a string $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. For example, bc, abc, and d are substrings of abcd, while ac and ba are not.

$$$^{\text{†}}$$$A string is a palindrome if it reads the same from left to right and from right to left. In other words, the reverse of the string is the same as the original string. For example, a, aba, and abba are palindromes, while ab and abc are not.

$$$^{\text{‡}}$$$String $$$x$$$ is lexicographically smaller than string $$$y$$$ if either $$$x$$$ is a proper prefix of $$$y$$$, or there exists a position $$$i$$$ ($$$1 \le i \le \min(|x|, |y|)$$$) such that $$$x_i \lt y_i$$$ and for all $$$j \lt i$$$, $$$x_j = y_j$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the string $$$b$$$.

The second line contains a binary string $$$b$$$ of length $$$n$$$ consisting of the characters 0 and 1.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print the lexicographically smallest valid string $$$s$$$, or $$$-1$$$ if no such string exists.

Example
Input
3
2
10
3
001
4
1111
Output
ab
-1
aaaa
Note

In the first test case, $$$b = \texttt{10}$$$. Every substring of length $$$1$$$ must be a palindrome, and the single substring of length $$$2$$$ must not be a palindrome. The lexicographically smallest such string is $$$\texttt{ab}$$$.

In the second test case, $$$b = \texttt{001}$$$. Since $$$b_1 = 0$$$ but a single character is always a palindrome, no valid string exists, so the answer is $$$-1$$$.

In the third test case, $$$b = \texttt{1111}$$$. Every substring, of every length, must be a palindrome. The lexicographically smallest such string is $$$\texttt{aaaa}$$$.