問題文

はちじくんは，友人の誕生日にプレゼントとして英小文字からなる文字列 $S$ を用意して渡すことにしました．

友人を驚かせようと，はちじくんは文字列 $S$ を連続する部分列として helloworld を含むように作ろうとしました．しかし，はちじくんは，作ろうとした文字列の一部を忘れてしまいました．

英小文字と，? からなる長さ $N$ の文字列 $S$ が与えられ，? ははちじくんがその箇所の文字を忘れたことを表します．はちじくんのために，? を英小文字に置き換えて，連続する部分列としてhelloworld を含む文字列を復元してください．ただし，そのような文字列が複数ある場合には，その中で辞書順最小のものを求め，そのような文字列が無い場合はその旨を報告してください．

$T$ 個のテストケースが与えられるので，それぞれに対して答えを求めてください．

入力

入力は以下の形式で標準入力から与えられる．

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

各ケースは以下の形式で与えられる．

$N$
$S$

制約

• $N, T$ は整数である．
• $1 \leq T \leq 20$
• $10 \leq N \leq 1000$
• $S$ は英小文字および ? のみからなる長さ $N$ の文字列である．

出力

$T$ 行にわたって出力せよ．$i(1 \leq i \leq T)$ 行目には $i$ 番目のテストケースについて，$S$ のうち ? である箇所を英小文字に変えることで連続する部分列として helloworld を含むようにすることが不可能ならば，-1 を出力せよ．可能ならば，そのような文字列の中で辞書順最小のものを出力せよ．

サンプル

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

ghelloworldad
-1
helloworld