Finn 正在玩一个名为“翻转并粘合”（Flip it and Stick it，简称 FiSi）的游戏。FiSi 是一个单人游戏，使用两个由 0 和 1 组成的字符串 $S$ 和 $T$ 进行。Finn 可以进行以下形式的操作：
- 选择 $S$ 的一个子串并将其反转，然后将各部分按原顺序粘合在一起，形成新的字符串 $S$。
例如，Finn 可以取字符串 $S = 101100$，选择从索引 2 开始的子串 $011$（假设使用 1-based 索引），并在一步操作内将其变为字符串 $S = 111000$。
如果 $S$ 不包含 $T$ 作为子串，则 Finn 获胜。你的任务是帮助 Finn 确定最短获胜操作序列的长度，或者告诉他该游戏无法获胜。
输入格式
第一行包含字符串 $S$ ($1 \le |S| \le 200\,000$)。 第二行包含字符串 $T$ ($1 \le |T| \le 3$)。
下表中，$T_1$ 是 $T$ 的第一个位，$T_2$ 是 $T$ 的第二个位，$T_3$ 是 $T$ 的第三个位（从左到右读取）。
| 分值 | $T$ 的范围 | ||
|---|---|---|---|
| 1 分 | $ | T | = 1$ |
| 3 分 | $ | T | = 2, T_1 \neq T_2$ |
| 4 分 | $ | T | = 2$ |
| 5 分 | $ | T | = 3, T_1 \neq T_3$ |
| 5 分 | $ | T | = 3, T_1 \neq T_2$ |
| 7 分 | $ | T | = 3$ |
输出格式
输出所需的最少操作次数，如果无法获胜，则输出 $-1$。
样例
样例输入 1
100110 10
样例输出 1
2
说明 1
Finn 从字符串 $100110$ 开始。他无法在一步操作内避免 $10$ 作为子串，但他可以在两步内做到。 例如，他的第一步操作可以是反转从索引 4 到索引 6 的子串 ($110$)，得到 $100011$。然后，他的第二步操作可以是反转从索引 1 到索引 4 的子串 ($1000$)，得到 $000111$，该字符串不包含 $10$ 作为子串。
样例输入 2
000 00
样例输出 2
-1
说明 2
无论 Finn 进行多少次操作，字符串 $S$ 始终包含 $T$ 作为子串。