题目描述

星期三在生日那天收到了一条很长的字符串 $s$。众所周知，星期三讨厌与折磨无关的礼物，因此看到这份糟糕的礼物后，她立刻想把它切成许多小块。不过，动手之前，她发现可以将字符串 $s$ 切开，再用得到的片段拼出两条受诅咒的字符串 $t_1$ 和 $t_2$，而这两条字符串正是她进行折磨时急需的东西。

星期三可以在字符串 $s$ 的任意位置切若干刀。随后，她准备两条初始为空的字符串 $a$ 和 $b$，按照这些片段在原字符串中从左到右的顺序依次处理：每个片段都必须追加到 $a$ 的末尾或 $b$ 的末尾。最终必须满足

星期三迫不及待地想拿到这两条受诅咒的字符串，开始她的折磨。请你求出，至少需要在 $s$ 上切多少刀，才能用上述方式得到 $t_1$ 和 $t_2$。

输入格式

第一行包含字符串 $s$，满足 $3\le |s|\le 10^4$。

接下来两行分别包含非空字符串 $t_1$ 和 $t_2$。

保证 $|t_1|+|t_2|=|s|$。所有字符串均只包含小写英文字母。

输出格式

输出一个整数，表示为了用上述方式得到 $t_1$ 和 $t_2$，最少需要在 $s$ 上切多少刀。保证一定存在答案。

wednesenidday
wednesday
enid

2

shadowednesdayw
wednesday
shadow

2

提示

样例 1 可以切成 wednes | enid | day。第一段和最后一段组成 $t_1$，中间一段组成 $t_2$。

样例 2 可以切成 shado | wednesday | w。第一段和最后一段组成 $t_2$，中间一段组成 $t_1$。