Pumpkins and Tombstones (part 1)

We are setting up a Halloween decoration in our front yard, which consists of carved pumpkins and tombstones. Here are our decoration rules:

The Halloween decoration is 1 or more slots long.
Zero or more of these slots are occupied by pumpkins.
There are $10$ types of pumpkin eyes (denoted by digits 0-9).
There are $10$ types of pumpkin mouths (denoted by letters A-J).
Two pumpkins in adjacent slots must have the same type of eyes, the same type of mouth, or both.
All the other slots are occupied by tombstones.
No two tombstones can be adjacent to each other.

We can conveniently record a decoration in string form by looking at slots from the first to the last, and writing down a T if the slot has a tombstone, and the pumpkin's eyes and mouth type (e.g., 2B) if the slot has a pumpkin.

We are considering several arrangements - can you help figure out which ones adhere to the rules described above?

Input

The first line contains an integer $T$ - the number of test cases.

Each of the following $T$ lines is a single non-empty string describing a decoration.

A slot with a tombstone is denoted with character T
A slot with a pumpkin is denoted with two characters [0-9][A-J]. For example, 2B is a pumpkin with eyes of type 2 and mouth of type B.
The string will contain at most $100$ characters.

All decorations are guaranteed to be validly encoded: every pumpkin is written as digit and letter ([0-9][A-J]), tombstones are T, and there are no stray characters.

Output

For each test case, print a single line Case #i: YES/NO, depending on whether the decoration in test $i$ follows our rules or not.

Examples

Input

4
T0AT9JT
0A0B1B
0ATT0B
0A9J

Output

Case #1: YES
Case #2: YES
Case #3: NO
Case #4: NO

Explanation

Case 1. Our T - 0A - T - 9J - T decoration consists of:

a tombstone
a pumpkin with eyes of type 0 and mouth of type A
a tombstone
a pumpkin with eyes of type 9 and mouth of type J
a tombstone

No two tombstones are adjacent, and no two pumpkins are adjacent.

Case 2. We have three adjacent pumpkins 0A - 0B - 1B. 0A and 0B have the same type of eyes. 0B and 1B have the same type of mouth.

Case 3. In decoration 0A - T - T - 0B, two tombstones are adjacent to each other, which is against the rules.

Case 4. In decoration 0A - 9J, the two adjacent pumpkins have different type of eyes and different type of mouth, which is against the rules.