暂无测试数据。

题目描述

雷古在翻阅《百年香的活用》时，发现了封底写着一个有趣的问题：

给出两个整数 $k,P$，递归定义一个合法括号序列 $S$ 的权值 $f(S)$：

• 将 $S$ 分成若干段，使得每一段都是合法括号序列，而且最左侧的括号和最右侧的括号匹配。（容易发现这样的分段方案唯一）
• 构造一个新的合法括号序列 $T$，由每一段去掉最外层的括号，不改变原有顺序拼接得到。设段数为 $x$。则 $f(S)=x^k+f(T)$
• 空括号序列的权值为 0。

比如 $S=\texttt{"(())()"}$，分成两段 $\texttt{"(())"}$，$\texttt{"()"}$，新的 $T=\texttt{"()"}$

找到最短的非空合法括号序列 $S$，使得 $f(S)$ 是 $P$ 的倍数。

雷古想知道这个最短长度，如果无解则输出 $-1$。

输入格式

一行两个整数 $P, k$。

输出格式

一行一个整数，表示最小答案；无解输出 $-1$。

数据范围

$1\le P\le 5000,0\le k\le 10^9$

数据点编号	P 的范围	k 的范围
1,2	$P\le 10$	$k\le 10$
3	$P\le 100$	$k \le 100$
4,5	$P\le 400$	$k\le 400$
6,7	$P\le 1000$	$k\le 5000$
8	$P\le 5000$	$k\le 1$
9,10	$P\le 5000$	$k\le 10^9$

3 1

6

5 2

6