Problem Description

In the anthology of 100 poems, there are 2 poems that start with "Wata no Hara," and the poem can only be determined by hearing the 6th character. In this way, when the smallest $q$ that satisfies "the first $q$ characters are unique among all the poems in the anthology" is $p$, the poem is said to be "determined by $p$ characters." For example, the 2 poems starting with "Wata no Hara" are determined by 6 characters.

Mathematician Takahashi-kun has extended the concept of being determined by $p$ characters to the true $p$ characters determination. A poem $S$ is truly determined by $p$ characters if the smallest $q$ that satisfies the following condition is $p$:

• No subsequence of length $q$ in $S$ is a subsequence of any other poem in the anthology.

Eager to use this true $p$ characters determination, Takahashi-kun decided to investigate the poems in Aoki-san's anthology "Hitori Futoshu." Hitori Futoshu consists of only 2 poems, $S$ and $T$, recited by Aoki-san. Determine for Takahashi-kun what true $p$ characters determination the poem $S$ has in "Hitori Futoshu." It is guaranteed that the two poems are not identical.

Input Format

The input is given from the standard input in the following format:

$ S $ $ T $

Output Format

When the poem $S$ is truly determined by $p$ characters, output $p$ in one line.

Sample Input and Output

Sample Input #1

abbcd
abccd

Sample Output #1

5

Sample Input #2

watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano

Sample Output #2

20

Notes/Hints

Constraints

• $ S $ and $ T $ are strings consisting only of lowercase English letters.
• $1 \leq |S| = |T| \leq 5000$
• $S \neq T$

见题面 Input 部分

见题面 Output 部分