The knight is standing in front of a long and narrow hallway. A princess is waiting at the end of it.

In a hallway there are three doors: a red door, a green door and a blue door. The doors are placed one after another, however, possibly in a different order. To proceed to the next door, the knight must first open the door before.

Each door can be only opened with a key of the corresponding color. So three keys: a red key, a green key and a blue key — are also placed somewhere in the hallway. To open the door, the knight should first pick up the key of its color.

The knight has a map of the hallway. It can be transcribed as a string, consisting of six characters:

R, G, B — denoting red, green and blue doors, respectively;

r, g, b — denoting red, green and blue keys, respectively.

Each of these six characters appears in the string exactly once.

The knight is standing at the beginning of the hallway — on the left on the map.

Given a map of the hallway, determine if the knight can open all doors and meet the princess at the end of the hallway.

Input

The first line contains a single integer t (1≤t≤720) — the number of testcases.

Each testcase consists of a single string. Each character is one of R, G, B (for the doors), r, g, b (for the keys), and each of them appears exactly once.

Output

For each testcase, print YES if the knight can open all doors. Otherwise, print NO.

Example

input

4

rgbBRG

RgbrBG

bBrRgG

rgRGBb

output

YES

NO

YES

NO

Note

In the first testcase, the knight first collects all keys, then opens all doors with them.

In the second testcase, there is a red door right in front of the knight, but he doesn't have a key for it.

In the third testcase, the key to each door is in front of each respective door, so the knight collects the key and uses it immediately three times.

In the fourth testcase, the knight can't open the blue door.

中文翻譯：

騎士站在一條狹長的走廊前。 一位公主在它的盡頭等待著。

走廊里有三扇門：紅門、綠門和藍(lán)門。 然而，這些門是一個接一個地放置的，順序可能不同。 要前往下一扇門，騎士必須先打開前面的門。

每扇門只能用相應(yīng)顏色的鑰匙打開。 因此，三把鑰匙：一把紅鑰匙、一把綠鑰匙和一把藍(lán)鑰匙——也被放置在走廊的某個地方。 要打開門，騎士應(yīng)該首先拿起其顏色的鑰匙。

騎士有一張走廊的地圖。 它可以轉(zhuǎn)錄為一個字符串，由六個字符組成：

R、G、B——分別表示紅、綠、藍(lán)門；

r、g、b——分別表示紅、綠、藍(lán)鍵。

這六個字符中的每一個都在字符串中恰好出現(xiàn)一次。

騎士站在走廊的盡頭——地圖的左邊。

給定一張走廊地圖，確定騎士是否可以打開所有門并在走廊盡頭與公主見面。

只要前面出線小寫的字母，后面匹配大寫的字母就可以的。也可以用string.indexof()去判斷也可以的，我是用的集合跟數(shù)量來判斷的；

下面是代碼：