Problem Statement

Hachiji-kun decided to prepare a string $S$ consisting of lowercase English letters and give it to his friend as a birthday present.

To surprise his friend, Hachiji-kun tried to make the string $S$ so that it contains helloworld as a contiguous subsequence. However, he forgot part of the string he was trying to make.

You are given a string $S$ of length $N$ consisting of lowercase English letters and ?, where ? indicates that Hachiji-kun forgot the character at that position. For Hachiji-kun, replace each ? with a lowercase English letter to restore a string that contains helloworld as a contiguous subsequence. If there are multiple such strings, find the lexicographically smallest one among them, and if there is no such string, report that.

You are given $T$ test cases; find the answer for each of them.

Input

The input is given from Standard Input in the following format.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each case is given in the following format.

$N$
$S$

Constraints

• $N, T$ are integers.
• $1 \leq T \leq 20$
• $10 \leq N \leq 1000$
• $S$ is a string of length $N$ consisting only of lowercase English letters and ?.

Output

Print $T$ lines. On the $i(1 \leq i \leq T)$-th line, for the $i$-th test case, print -1 if it is impossible to make the string contain helloworld as a contiguous subsequence by changing the positions of ? in $S$ to lowercase English letters. If it is possible, print the lexicographically smallest such string.

Sample

3
13
g?e??owo??d?d
26
abcdefghijklmnopq?????????
10
helloworld

ghelloworldad
-1
helloworld