Sedrak likes making various things from paper (and he's very good at that). But after he finishes the job, his table is covered with a lot of useless creased, scrappy paper. Can he use them somehow?

Imagine a thin strip of paper marked with creases at regular intervals, which we can think of as a line segment divided into equal-length subsegments. Each crease point is marked with as mountain, valley, or flat to specify the orientation of the crease (∧, ∨, -). For example the input might look as follows:

Sedrak thinks, he can use the scrap, if it is possible to fold it using all the marked creases with the specified orientations. The operations he is allowed are as follows. Given a particular crease (∧ or ∨), simple fold rotates the portion of the segment to the left of the crease around the portion of the segment to the right of the crease. The rotation is counterclockwise for a mountain fold, and clockwise for a valley fold. When multiple layers of paper come in contact, they become inseparable; in other words, each simple fold must fold all layers of paper. For example, here is how he might fold the example above:

Notice that when a subsegment is folded, the crease turns upside-down, inverting ∧↔∨. Thus, for a simple fold to be valid, the inversions of the creases to the left must match the creases to the right.

Input

The first line of input file contains the number 1 ≤ N ≤ 20 - the number of paper scraps on Sedrak’s table. Next N lines contain descriptions of paper scraps as a string containing symbols ‘^’, ‘v’ and ‘-‘. The length of a single description does not exceed 10^6.

Output

For each description line of the input file, output a single line containing “Yes”, if Sedrak can use the scrap, and “No” otherwise.

Example

Input:
6
-^vv-
--v-
-vv-
^vv^
v-v^-^^
--^-v^^-v--

Output:
Yes
Yes
No
Yes
No
Yes

NOTE: The last example corresponds to the scrap in the figure.