题目描述

小明在研究约数，他发现一个数的约数中，有一些约数恰好是一个平方数。他将这些约数称作“平方约数”

例如600的约数中，$4=2^2$、$25=5^2$ 和 $100=10^2$是“平方约数”。

给出整数n,m，小明想要知道$n,n^2,n^3,\ldots$中，第一个拥有至少m个“平方约数”的数是哪一个？

你需要输出使得 $n^b$ 拥有至少 $m$ 个“平方约数”的最小正整数 $b$。

输入格式

第1行，两个正整数n,m

输出格式

若不存在满足条件的正整数 b，输出 -1。特别地，当 n=1 且 m>1 时没有解。

输出使得 $n^b$ 拥有至少 $m$ 个“平方约数”的最小正整数 $b$。

6 12

6

8 3

2

6 4

2

数据范围与约定

$1\le n,m\le 10^{12}$