Storage Device

Time limit2sMemory limit512 MB

Summary

Decide whether string s can become t by repeatedly flipping the shorter of two adjacent runs of unequal length in a +/- sequence.

Level: Medium7 of 10
Topics: String, Simulation, Greedy
Solved: No attempts yet

Problem

A new digital information storage device is being studied. Information is stored as a row of cells, each in one of two states, written as + and -. Each cell therefore holds one bit.

A fragment is a group of adjacent cells with the same state. The cell to its left is either absent or has the opposite state, and the cell to its right is either absent or has the opposite state.

A write operation selects a pair of adjacent fragments of different lengths and flips the state of every cell in the shorter fragment. This merges two or three adjacent fragments into one.

Given an initial and a target sequence of cell states, write a program that determines whether the target can be obtained from the initial sequence by applying write operations in order.

Input

The first line contains the integer $q$ , the number of tests. Each of the next $q$ lines contains $s_i$ and $t_i$ , two nonempty strings of + and - of equal length, separated by one space. In test $i$ , the sequence $s_i$ must be turned into $t_i$ .

Output

Print $q$ lines. The $i$ -th line is Yes if $t_i$ can be obtained from $s_i$ , and No otherwise.

Examples2

Example 1

Input

3
++- +++
++-- ++++
++-+--+- ++++++++

Expected output

Yes
No
Yes

Example 2

Input

3
++-+-- ++----
++-+-- +++---
-++- -++-

Expected output

Yes
No
Yes