解题思路

问题转化

设最终把整数 $n$ 拆成了：

• $x$ 个素数 $2$
• $y$ 个奇素数

题目内容

给定一个正整数 $n$ 与一个正整数 $m$ 。你需要把 $n$ 拆分为若干个素数之和(可以重复选择同一个素数)，设最终使用的素数个数为 $k$ 。

同时要求：所选素数中奇素数(除 $2$ 以外的素数)的数量必须是 $m$ 的正整数倍(不能为 $0$ )。

请在满足约束的前提下，使 $k$ 最大化，并输出这个最大的 $k$ 。若不存在任何满足要求的拆分方案，输出 $-1$。

【名词解释】

• 素数：大于 $1$ 且只有 $1$ 与其本身两个正因子的整数;

• 奇素数：除 $2$ 以外的素数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ 表示测试数据组数，每组测试数据描述如下：

在一行上输入两个整数 $n,m(2≤n≤10^{18};1≤m≤10^{18})$.

输出描述

对于每一组测试数据，新起一行输出一个整数：满足要求的最大的素数个数 $k$ ；若无解，则输出 $-1$ 。

样例1

输入

4
6 2
2 1
30 4
1000000000000 1

输出

2
-1
13
499999999999

说明

对于第一组样例 $6$ 可以拆分为 $3+3$ 。