You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

ikun热爱原神，尤其钟情于前瞻直播！每次直播，他都满怀期待，不是为了那诱人的300原石兑换码，而是为了深入了解新卡池的角色与武器强度，以及那些新角色是否能触动他的心弦。最近一次直播中，尽管希诺宁姐姐的魅力无法抵挡，ikun依然保持正直，专注于他的兑换码梦想。不仅如此，他还意外发现了一个兑换码有一个趣的秘密——一个充满魔力的字符串性质！原神的魅力，真是无处不在，连字符串都藏着惊喜！

给定一个字符串 $S$，将 $S$ 自身重复 $n$ 次得到一个字符串 $T$，则称 $T$ 为 $S$ 的循环字符串，记为 $T = S^n$ ($n\gt0$)。例如，$S='123'$,则 $S^3 = '123123123'$。

此外，字符串转换为数值的操作定义为 $eval(T)$。例如，$eval('123') = 123$。

现在，要求找到满足 $eval(T) \mod x = 0$ 的最小 $n$ 值($x$是质数)。如果不存在这样的 $n$，则输出 -1。

Input Format

第一行输入整数$x$ ($2 \leq x \leq 10^6$)($x$是质数)。

第二行输入字符串$S$ ($len=3$)。

Output Format

输出最小的$n$值,若不存在输出-1。

Sample

输入 #1

3
111

输出 #1

1

输入 #2

7
123

输出 #2

2

输入 #3

2
113

输出 #3

-1

样例1:当$T=S^1$,即$T='111'$,$111\%3=0$,不存在$n\lt1$使其成立。

样例2:当$T=S^2$,即$T='123123'$,$123123\%7=0$,不存在$n\lt2$使其成立。

样例3:可以证明不存在这样的$n$使其成立。