Under construction

Still being built. Things may change

The Grand Adventure

Interview

Time limit1sMemory limit1024 MB

Summary
Given strings of items and villains, decide whether Jim can pay each villain the top item of a stack and finish with an empty backpack.
Level

Easy3 of 10

Topics
Stack, Simulation
Solved
No attempts yet

Problem

Our hero, Jim, is about to start his grand adventure. On the way, he will meet three kinds of objects: money, incense, and gems. Whenever he meets an object, he always puts it into his backpack. He will also meet villains along the way: the Banker, who demands money, the Trader, who demands incense, and the Jeweler, who demands jewels. Each time Jim meets a villain, he must give that villain one item of the kind they demand, or he fails and the adventure ends. The backpack is awkward, so Jim can only reach the item he most recently put in. Items below stay inaccessible until the item on top is given away. Jim also wants to arrive at his destination with an empty backpack. If any items remain at the end, the adventure counts as a failure.

We want to know, before Jim even starts, whether he can complete his adventure.

Input

The first line contains a single integer n, 1 ≤ n ≤ 5, the number of adventures. Each of the next n lines contains one string a made of the characters {$, *, |, t, j, b}. An example of such a string is:

....$...$...*..*...|...t...j..j...b..b...

The characters mean the following:

  • $ is Money
  • | is Incense
  • * is a Gem
  • t is a Trader
  • j is a Jeweler
  • b is a Banker
  • . is the Ground (nothing)

The length of each string satisfies 1 ≤ |a| ≤ 100. The backpack has no limit on the number of items.

Output

For each adventure, print YES if Jim can finish it, and NO if he cannot.

Examples2

  1. Example 1

    Input
    5
.$.b.|.t.*.j.................$$$$$bbbbb||....tt.....
.$.b.|.t.*.j..
................................
.......$....$......*....*.....|......t........j...j.....b..b........
...$.$.$..*..*..*...*..|..*..b.....*******...
    Expected output
    YES
YES
YES
YES
NO

  2. Example 2

    Input
    4
........$b...$$..t...*..*...j.........j...
.........*****jjjj...............|tj....
.$.|.*.$.|.*.$.|.*.j.t.b.j.t.b.j.t.b.
...$$..$$..$$..|..$$..b......b....t..bbbbbb.....j...
    Expected output
    NO
YES
YES
NO