Universal Question Answering System

Input

The input consists of several dialogues.

The first line contains a single positive integer $T$ (T \leq 500, but note that $95\%$ of them are relatively small). It denotes the number of dialogues. Each dialogue consists of one or more lines. Each line contains a sentence: either a statement or a question. Statements end with a dot ($.$), while questions end with a question mark ($?$). After each dialogue, there is an extra line that ends with an exclamation mark ($!$). The definitions of statements and questions will be discussed later.

Sentences can contain words, spaces, and punctuation marks. All words consist only of Latin letters and are case-sensitive. Unlike the normal rules of English writing, the first letter of a sentence should remain lowercase unless the first word itself must begin with a capital letter. There are no extra spaces between words. No word will have more than $10$ characters. There will be at most $1000$ lines in any dialogue.

Statements

Each statement has one of the following forms:

noun_phrase are noun_phrase. noun_phrase can verb_phrase. everything which can verb_phrase can verb_phrase. everything which can verb_phrase are noun_phrase.

Here, noun_phrase and verb_phrase are both single words. The meanings of the four forms are:

$A$ are $B$: If $X$ is $A$, then $X$ is $B$.

$A$ can $B$: If $X$ is $A$, then $X$ can $B$.

everything which can $A$ can $B$: If $X$ can $A$, then $X$ can $B$.

everything which can $A$ are $B$: If $X$ can $A$, then $X$ is $B$.

Questions

Each question has one of the following forms:

are noun_phrase noun_phrase? can noun_phrase verb_phrase? can everything which can verb_phrase verb_phrase? are everything which can verb_phrase noun_phrase?

These are the question forms of the statements.

In each test case, the number of different noun phrases will not exceed $100$, and the number of different verb phrases will not exceed $100$.

Output

For each test case, output two lines. The first line describes the test case number, starting from $1$, and the second line contains as many characters as the number of questions in this test case. Each character is either Y (meaning you can logically obtain that fact) or M (otherwise), without quotes.

Examples