Two Screens
Contest: Educational Codeforces Round 170 (Rated for Div. 2)
Difficulty rating: 800
Tags: binary search, greedy, strings, two pointers

There are two screens which can display sequences of uppercase Latin letters. Initially, both screens display nothing.

In one second, you can do one of the following two actions:

- choose a screen and an uppercase Latin letter, and append that letter to the end of the sequence displayed on that screen;
- choose a screen and copy the sequence from it to the other screen, overwriting the sequence that was displayed on the other screen.

You have to calculate the minimum number of seconds you have to spend so that the first screen displays the sequence $$$s$$$, and the second screen displays the sequence $$$t$$$.

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of test cases.

Each test case consists of two lines. The first line contains the string $$$s$$$, and the second line contains the string $$$t$$$ ($$$1 \le |s|, |t| \le 100$$$). Both strings consist of uppercase Latin letters.

Output format:
For each test case, print one integer — the minimum possible number of seconds you have to spend so that the first screen displays the sequence $$$s$$$, and the second screen displays the sequence $$$t$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the following sequence of actions is possible:

- spend $$$6$$$ seconds to write the sequence GARAGE on the first screen;
- copy the sequence from the first screen to the second screen;
- spend $$$7$$$ seconds to complete the sequence on the second screen by writing FORSALE.

In the second test case, the following sequence of actions is possible:

- spend $$$1$$$ second to write the sequence A on the second screen;
- copy the sequence from the second screen to the first screen;
- spend $$$4$$$ seconds to complete the sequence on the first screen by writing BCDE;
- spend $$$4$$$ seconds to complete the sequence on the second screen by writing ABCD.

In the third test case, the fastest way to display the sequences is to type both of them character by character without copying, and this requires $$$16$$$ seconds.

Example input:
3
GARAGE
GARAGEFORSALE
ABCDE
AABCD
TRAINING
DRAINING

Example output:
14
10
16

Editorial:
Whenever we perform the second action (copy from one screen to the other screen), we overwrite what was written on the other screen. It means that we can consider the string on the other screen to be empty before the copying, and that we only need to copy at most once.
So, the optimal sequence of operations should look as follows: add some characters to one of the screens, copy them to the other screen, and then finish both strings.
We need to copy as many characters as possible. Since after copying, we can only append new characters to the end of the strings on the screens, the string we copy must be a prefix of both of the given strings. So, we need to find the length of the longest common prefix of the given strings. This can be done in linear time if we scan these strings until we find a pair of different characters in the same positions; however, the constraints were low enough so that you could do it slower (like, for example, iterate on the length of the prefix and check that both prefixes of this length are equal).
Okay, now let $$$l$$$ be the length of the longest common prefix. Using $$$l+1$$$ operations, we write $$$2l$$$ characters in total; so the number of operations we need will be $$$|s|+|t|-2l+l+1 = |s|+|t|+1-l$$$. However, if the longest common prefix is empty, there's no need to copy anything, and we can write both strings in $$$|s|+|t|$$$ seconds.