Wielka Przesmycka 2011 Eternal

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).

Bounds

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

Output one line containing the length of the best therapy.

Sample input for the basic version

1
1010011101
0011010110

Sample output for the basic version

6

Sample input for the professional version

1
0120212102120
2020120012012

Sample output for the professional version

6