H. Happy Morse Code
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little Rabbit and Little Horse recently learned about Morse code and found that just only two symbols of dash and dot can express countless words, for that each letter has a unique dash-dot string correspondence. Little Rabbit and Little Horse get the wrong conclusion because a dash-dot string does not necessarily correspond to a letter, it may also correspond to a number, or it may correspond to a sentence indicating start, interrupt, and end.

Anyway, they plan to use 0 to represent a dot, 1 to represent dash, and binary strings to express their own happy Morse code. They randomly assign a binary string for each letter and made it into a cipher book.

Given a binary string, can Little Rabbit and Little Horse's cipher book uniquely interpret the meaning of the string? If it is, output happymorsecode; if there is more than one possible interpretation, output puppymousecat and the number of feasible interpretations modulo $$$128$$$; if it can't be interpreted at all, output nonono.

Input

The input contains several test cases.

The first line contains a single integer $$$T\ (1\le T\le 10^5)$$$, indicating the number of test cases.

For each test case: the first line contains two integers $$$n\ (1\le n\le 10^5)$$$ and $$$m\ (1\le m\le 26)$$$, indicating the length of the given binary string $$$s$$$ and the number of letters in the cipher book. For the following $$$m$$$ lines, each line contains a unique letter and its binary string correspondence $$$t\ (1\le |t|\le 5)$$$, where $$$|t|$$$ denotes the length of string $$$t$$$. The last line contains the given binary string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ will not exceed $$$10^5$$$.

Output

For each test case, output following content in a line: if the cipher book can interpret the unique meaning of the string, output happymorsecode; if the book can interpret more than one meanings of the string, output puppymousecat and the number of feasible interpretation modulo $$$128$$$; if the string can't be interpreted at all, output nonono.

Example
Input
3
4 2
a 01
b 10
0110
4 4
a 01
b 10
c 01
d 0110
0110
4 2
a 1
b 10
0110
Output
happymorsecode
puppymousecat 3
nonono