TokyoTech Programming Contest 每年举办一次。现有四个大写英文字符串 $S_1, S_2, S_3, S_4$。从明年开始，第 $x$ 年后举办的 TokyoTech Programming Contest 的缩写 $T_x$ 由以下规则确定：

• $T_x$ 是一个由四个大写英文字符组成的字符串。
• $T_x$ 的第 $i$ 个字符（$1 \le i \le 4$）等于 $S_i$ 的第 $(((x-1) \pmod{|S_i|}) + 1)$ 个字符。（其中 $|S_i|$ 表示字符串 $S_i$ 的长度）。

给定一个正整数 $N$。请问在多少年后，缩写将第 $N$ 次变为 TTPC？

输入格式

输入通过标准输入给出，格式如下：

$N$ $S_1$ $S_2$ $S_3$ $S_4$

• $N$ 是一个整数。
• $1 \le N \le 10^6$
• $1 \le |S_i| \le 10^3$ ($1 \le i \le 4$)
• $S_i$ ($1 \le i \le 4$) 由大写英文字符组成。

输出格式

输出一个满足以下两个条件的正整数 $x$。如果不存在这样的 $x$，则输出 -1。

• $T_x = \text{TTPC}$
• 字符串 TTPC 在 $T_1, T_2, \dots, T_x$ 中总共出现了 $N$ 次。

样例

样例输入 1

3
TTPC
TLE
P
AC

样例输出 1

34

样例输入 2

670055
TF
OITFKONTO
GFPPNPWTZP
CCZFB

样例输出 2

-1

样例输入 3

910359
TOKYO
TECH
PROGRAMMING
CONTEST

样例输出 3

1401951321

说明

在第一个样例中，缩写在 10 年后第一次变为 TTPC，在 22 年后第二次变为 TTPC，在 34 年后第三次变为 TTPC。因此答案是 34。

在第二个样例中，缩写 TTPC 永远不会出现。