Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

WPFF - F It sometimes is lupus (professional)

There are two acknowledged therapies for lupus. Each treatment requires the patient to take doses of three drugs (which we will denote here by 0, 1 and 2) for a certain number of days (the same for both therapies) in a fixed order: every day, the patient receives a dose of the drug 0, 1 or 2. Therefore, a therapy can be represented as a sequence, for example 2001120011.

The therapies are quite effective. However, due to the large discrepancy between them, they are considered to be a conspiracy of pharmaceutical companies. It is suspected that skipping some of the doses would not decrease the effectiveness of the therapy at all. What's worse, the therapies have some very severe side effects: after a few days of therapy, the patient's head starts to feel like a frisbee.

It turns out that drug 0 contains a small dose of intoxicants, drug 1 contains some more, and drug 2 contains quite a lot. Basing on the rich and personal experience gained during many years of medical studies, your team figured out a way to neutralise the side effects: after taking drug 1 a patient should never take drug 0, and after taking drug 2 - neither drug 0 nor 1. Your task is to prepare a therapy which: is the longest possible, can be obtained from each of the two therapies by skipping some doses and does not cause side effects. For example, if the two existing therapies are 0120212102120 and 2020120012012, the best therapy is 001122.

Multiple test cases

The first line of the input contains Z ≤ 20 - the number of test cases. Z descriptions of single test cases follow.

Single test case

There are two lines in the input, each containing a description of one therapy as a sequence of digits 0, 1 and 2 (not separated with spaces).


Common: the description of each therapy has length at most 1000000.
Basic: none of the descriptions contain the digit 2.
Professional: the descriptions might contain all three digits.


Output one line containing the length of the best therapy.

Sample input for the basic version


Sample output for the basic version


Sample input for the professional version


Sample output for the professional version


Added by:gawry
Time limit:0.100s-3.782s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.