题目内容

冷链调度中心要把总时长恰好为 $n$ 分钟的保温任务切成若干段。每一段的时长必须是一个素数，同一素数可以重复使用。设一共切出 $k$ 段，其中时长为奇素数（除 2 以外的素数）的段数必须是 $m$ 的正整数倍，且不能为 0。规程希望段数 $k$ 尽可能大，以便更密地插入测温节点；若不存在任何合法切分，则判定无法排程。请输出最大的 $k$；无解时输出 -1。

素数指大于 1 且只有 1 与自身两个正因子的整数；奇素数指除 2 以外的素数。

约束：测试组数不超过 10000；每组满足 $2 \le n \le 1000000000000000000$、$1 \le m \le 1000000000000000000$。

输入描述

第一行一个整数 $t$，表示测试组数。 接下来 $t$ 行，每行两个整数 $n$ 和 $m$，表示总时长与倍数约束。 保证 $1 \le t \le 10000$，$2 \le n \le 1000000000000000000$，$1 \le m \le 1000000000000000000$。

输出描述

对每组数据输出一行一个整数：最大段数；无解则输出 -1。

样例1

输入

3
9 1
4 2
20 1

输出

4
-1
9

说明

三组数据：

• $n=`9`,m=`1`$：最小合法奇素数个数 $y=`1`$，答案为 $(9-1)/2=`4`$；
• $n=`4`,m=`2`$：$m$ 为偶数且 $n$ 为偶数，但 $3y=`6`>`4`$，无解，输出 -1；
• $n=`20`,m=`1`$：$n$ 与 $m$ 异奇偶，取 $y=`2`$，答案为 $(20-2)/2=9。

样例2

输入

2
8 3
11 2

输出

-1
-1

说明

两组数据：

• $n=`8`,m=`3`$：取 $y=`6`$，$3y=`18`>`8`$，无解；
• $n=`11`,m=`2`$：$m$ 为偶数而 $n$ 为奇数，奇偶无法匹配，输出 -1。