フリーランスとしての仕事はかつてないほど順調で、あなたはハンモックに揺られながら飲み物を片手に、次の仕事の依頼リストをのんびりと眺めていました。その時、ふと奇妙な依頼が目に留まりました。いや、奇妙という言葉では足りないかもしれません。ある作家が「言葉」を探しているのです。それも普通の言葉ではなく、非常に珍しい言葉を必死に求めているようです。あなたは、これほど奇妙なものをプログラミングで扱う経験を積んだ人間は他にいないだろうと思い、この仕事を引き受けることにしました。

翌日、詳細が送られてきました。依頼主は現在、次回作の執筆に行き詰まっている著名な作家です。それも、彼の作品を原作としたテレビシリーズの最終シーズンがすでに放送されてしまうほど、深刻な行き詰まりです。秘密保持契約に署名した後、事態は見た目よりも複雑であることを知りました。本自体は数年前からほぼ完成していましたが、それ以来、作家は決して納得のいくものにならないある章を書き直し続けているのです。その章は、全く同じ長さの3つの単語による非常に複雑な言葉遊びを軸とした、重要な予言に関するものです。

あなたは、最初の単語 $s$ が最後の単語 $t$ よりも辞書順で小さく、かつそれらが同じ長さであることを知っています。依頼主は、$s$ と $t$ の間に辞書順で厳密に位置し、かつ予言された英雄の名前の最初の文字である文字 $K$ を含む、同じ長さの単語 $x$ を見つけてほしいと言っています。そのような単語 $x$ が存在しない可能性もあります（それが執筆の遅延の理由を完全に説明するのですが……さて、どうなるでしょうか）。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 100\,000$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、$s$ と $t$ の長さである整数 $n$ ($1 \le n \le 25\,000$) と、小文字のアルファベット $K$ が含まれます。続く2行には、英小文字からなる単語 $s$ と $t$ がそれぞれ与えられます。

すべてのテストケースにおける $n$ の総和は $100\,000$ を超えません。

出力

各テストケースについて、条件を満たす長さ $n$ の英小文字からなる単語 $x$ を1行で出力してください。そのような単語が存在しない場合は「NO」と出力してください。

入出力例

入力 1

4
10 m
christmasa
christmasx
6 m
spring
winter
21 a
ithinkthereforeisleep
ithinkthereforeithink
3 z
tcs
tcz

出力 1

christmass
summer
ithinkthereforeistand
NO