Ceci est un problème interactif.

Alice et Bob jouent à un jeu avec une chaîne binaire $s$ et un entier fixe $k$. Au début, il y a une chaîne vide $t$. Les joueurs ajoutent à tour de rôle un caractère (0 ou 1) à la fin de $t$, en commençant par Alice.

L'interaction continue toujours jusqu'à ce qu'exactement $k$ caractères aient été ajoutés à $t$. Alice gagne si et seulement si la chaîne finale $t$ contient $s$ comme sous-chaîne contiguë. Sinon, Bob gagne.

Vous pouvez choisir de jouer en tant qu'Alice ou Bob. Votre objectif est de gagner la partie contre le jury.

Interaction

Chaque exécution de test contient plusieurs cas de test. Vous devez d'abord lire une ligne contenant un entier $T$ ($1 \le T \le 100$), représentant le nombre de cas de test.

Pour chaque cas de test, vous commencez l'interaction en lisant une chaîne binaire $s$ et un entier $k$ sur une seule ligne ($1 \le |s| \le k \le 100$), indiquant le nombre de tours et les paramètres du jeu. Ensuite, affichez un mot : Alice si vous choisissez de jouer en tant qu'Alice, ou Bob si vous choisissez de jouer en tant que Bob. Après cela, le jeu commence avec la chaîne vide. Alice fait le premier coup. Chaque fois que c'est à votre tour, affichez un caractère, soit 0, soit 1. Chaque fois que c'est au tour du jury, lisez un caractère, soit 0, soit 1. Le jeu se termine lorsque la chaîne courante a une longueur $k$.

Après chaque opération de sortie, vous devez vider le tampon de sortie. Par exemple, en C++, vous pouvez utiliser cout << endl; ou cout.flush();.

Si vous affichez un jeton invalide, jouez un coup après la fin du jeu, oubliez de vider le tampon, ou perdez la partie, vous recevrez le verdict Wrong Answer.

Remarque

Le tableau suivant montre une interaction possible pour l'exemple. Les lignes dans la colonne « Jury » sont lues par le programme du candidat, et les lignes dans la colonne « Candidat » sont affichées par le programme du candidat.