Travailler en tant que freelance n'a jamais été aussi simple, vous dites-vous, allongé dans un hamac en sirotant une boisson, tout en faisant défiler paresseusement la page suivante des demandes de travail. Soudain, vous remarquez une demande inhabituelle. Je dirais même étrange. Un écrivain est à la recherche d'un... mot. Non, pas un mot ordinaire, il a désespérément besoin d'un mot inhabituel. Vous décidez d'accepter ce travail. Après tout, qui est plus expérimenté que vous pour programmer des choses étranges ?

Le lendemain, vous obtenez tous les détails. La demande provient d'un auteur renommé qui est actuellement bloqué dans l'écriture de son prochain roman. Vraiment bloqué... au point que la dernière saison de la série télévisée basée sur son œuvre a déjà été diffusée. Après avoir signé un accord de confidentialité, vous apprenez que la vérité est plus compliquée qu'il n'y paraissait. Le livre est en fait presque terminé depuis plusieurs années déjà, mais depuis lors, l'auteur n'a cessé de réécrire un seul chapitre qu'il n'arrive jamais à rendre parfait. Le chapitre tourne autour d'une prophétie cruciale, conçue comme un jeu de mots très complexe sur trois mots de longueur exactement identique.

Vous savez que le premier mot $s$ est lexicographiquement plus petit que le dernier mot $t$ et qu'ils ont le même nombre de caractères. Votre client souhaite trouver un mot $x$ de la même longueur, qui est strictement compris entre $s$ et $t$ d'un point de vue lexicographique, et qui contient en même temps la première lettre du nom du héros promis : le caractère $K$. Il est possible qu'un tel mot $x$ n'existe pas (ce qui expliquerait pleinement tous les retards), mais... qui sait ?

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 100\,000$). Les descriptions des cas de test suivent.

La première ligne d'un cas de test contient un entier $n$ – la longueur de $s$ et $t$ ($1 \le n \le 25\,000$) – et une lettre minuscule $K$. Les deux lignes suivantes contiennent les mots $s$ et $t$, composés de lettres minuscules de l'alphabet anglais.

La somme de $n$ sur tous les cas de test ne dépasse pas $100\,000$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant une chaîne : n'importe quel mot $x$ de longueur $n$, composé de lettres minuscules de l'alphabet anglais, qui répond aux exigences, ou « NO » si aucun mot de ce type n'existe.

Exemples

Entrée 1

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

Sortie 1

christmass
summer
ithinkthereforeistand
NO