Kruskal-chan is deep in thought at the whiteboard in the clubroom today.

"Hmm... walking around on a tree and finally returning to the starting point, does such a tree really exist?"

Her junior leans over curiously: "Is the senior researching strange problems again?"

"It's not strange at all!" Kruskal-chan puffs out her cheeks, "This is a key problem that determines whether I can return to the origin!"

She stares at the sequence of actions in her hand, her fingertips tapping lightly on the desk.

"If I could find such a tree, it would be very interesting ~"

A rooted tree $R$ has nodes labeled with distinct positive integers. Kruskal-chan is initially located at some node in $R$, and she can perform the following four types of actions:

• Move to the parent node, denoted by p
• Move to any child node, denoted by c
• Move to any sibling node with a smaller label, denoted by l
• Move to any sibling node with a larger label, denoted by r

Given a sequence of actions, determine whether there exists a tree $R$ such that, by appropriately choosing the initial node and the target node for each action, Kruskal-chan can return exactly to the initial node after performing all actions.

Note: You must ensure that your construction is valid at every step. For example, if you are currently at the root node, you cannot perform a p action.

Input

The input contains multiple test cases.

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

Then $T$ lines follow, each containing a non-empty string consisting only of the characters p, c, l, and r, representing the sequence of actions.

It is guaranteed that the sum of the lengths of the action sequences does not exceed $10^5$.

Output

Output $T$ lines, representing the result for each test case. If a tree $R$ satisfying the problem requirements exists, output Yes, otherwise output No.

Examples

Input 1

4
l
lr
ppc
cppc

Output 1

No
Yes
No
Yes

Note

For the first and third test cases, it can be proven that it is impossible to return to the initial node.

The figure below shows a tree that satisfies the second test case, where the root node is labeled 2, the initial node is labeled 4, and the action sequence is $4 \to 1 \to 4$ or $4 \to 3 \to 4$.

The figure below shows a tree that satisfies the fourth test case, where the root node is labeled 2, the initial node is labeled 1, and the action sequence is $1 \to 4 \to 1 \to 2 \to 1$.