作为一名自由职业者，工作从未如此轻松。你正躺在吊床上喝着饮料，懒洋洋地浏览着下一页的工作请求。突然，你注意到一个不同寻常的请求。我甚至得说，这是一个奇怪的请求。一位作家正在寻找一个……词。不，不是普通的词，他迫切需要一个不同寻常的词。你决定接下这份工作。毕竟，还有谁比你更有经验去编写这些奇怪的东西呢？

第二天，你得到了所有细节。这个请求来自一位著名的作家，他目前正卡在下一部小说的创作中。就像真的卡住了一样……以至于根据他的作品改编的电视剧的最后一季都已经播出了。在签署了保密协议后，你了解到真相远比看起来复杂。这本书实际上已经完成了好几年了，但从那以后，作者一直在重写一个他永远无法写好的章节。这一章围绕着一个关键的预言，旨在对三个长度完全相同的词进行非常复杂的文字游戏。

你知道第一个词 $s$ 在字典序上早于最后一个词 $t$，且它们具有相同的字符数。你的客户想要找到一个长度相同的词 $x$，它在字典序上严格介于 $s$ 和 $t$ 之间，同时包含预言中英雄名字的首字母：字符 $K$。有可能这样的词 $x$ 并不存在（这完全可以解释所有的延误），但是……谁知道呢？

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 100\,000$)。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ —— $s$ 和 $t$ 的长度 ($1 \le n \le 25\,000$) —— 以及一个小写字母 $K$。接下来的两行包含单词 $s$ 和 $t$，由小写英文字母组成。

所有测试用例中 $n$ 的总和不超过 $100\,000$。

输出格式

对于每个测试用例，输出一行，包含一个长度为 $n$、由小写英文字母组成的字符串 $x$，该字符串满足上述要求；如果不存在这样的词，则输出 “NO”。

样例

输入 1

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

输出 1

christmass
summer
ithinkthereforeistand
NO