Description

Mushroom最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力，Mushroom决定不手写情书。他从网上找到了两篇极佳的情书，打算选择其中共同的部分。另外，Mushroom还有个一个情敌Ertanis，此人也写了封情书给妹子。

Mushroom不希望自己的情书中完整的出现了情敌的情书。（这样抄袭的事情就暴露了）。

Mushroom把两封情书分别用字符串s1和s2来表示，Ertanis的情书用字符串s3来表示，他要截取的部分用字符串w表示。

需满足：

1、w是s1的子串

2、w是s2的子串

3、s3不是w的子串

4、w的长度应尽可能大

所谓子串是指：在字符串中连续的一段

【输入】

输入文件为girl.in

输入有三行，第一行为一个字符串s1第二行为一个字符串s2，

第三行为一个字符串s3。输入仅含小写字母，字符中间不含空格。

【输出】

** **输出文件为girl.out

** **输出仅有一行，为w的最大可能长度，如w不存在，则输出0。

【输入样例】

abcdef

abcf

bc

【输出样例】

2

【样例解释】

s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。

【数据规模】

对于30%的数据：1<=s1、s2、s3的长度<=500

对于60%的数据：1<=s1、s2、s3的长度<=5000

对于100%的数据：1<=s1、s2的长度<=50000,1<=s3的长度<=10000

Format

Input

输入有三行，第一行为一个字符串s1第二行为一个字符串s2，

第三行为一个字符串s3。输入仅含小写字母，字符中间不含空格。

Output

输出仅有一行，为w的最大可能长度，如w不存在，则输出0。

Samples

abcdef
abcf
bc

2
【样例解释】
s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。

Limitation

对于100%的数据：1<=s1、s2的长度<=50000,1<=s3的长度<=10000