质数

题号：NC295396
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给你 $q$ 次询问，每次询问给出两个整数 $l,r$ ，现在需要你将区间 $[l,r]$ 内所有数分别放入两个集合 $\Bbb{S_1},\Bbb{S_2}$ 其中之一，最终需要满足：
$\hspace{15pt}\bullet\,$ $\Bbb{S_1},\Bbb{S_2}$ 两个集合都至少有一个数，并且满足 $\gcd (\Bbb{S_1})=1$ 且 $\gcd (\Bbb{S_2})\ne 1$ 。
$\hspace{15pt}$ 现在，对于每次询问，在满足上述条件的情况下，求出 $\left\lvert \operatorname{len}(\Bbb{S_1})-\operatorname{len}(\Bbb{S_2})\right\rvert$ 的最小值，如果没有满足的情况，则输出 $-1$ 。

$\hspace{15pt}$ 注：若集合 $\Bbb{S}=\{3\}$ ，则 $\gcd(\Bbb{S})=\gcd(3)=3$ ；若集合 $\Bbb{S}=\{6,9,12\}$ ，则 $\gcd(\Bbb{S})=\gcd(6,9,12)=3$ ，其中 $\gcd$ 表示集合内所有数的最大公因数。

输入描述:

第一行输入一个整数  ，表示询问次数。 
此后  行，第  行输入两个整数  ，表示第  次询问的区间。

输出描述:

对于每次询问，新起一行输出一个整数，表示  的最小值，如果没有满足的情况，则输出 。

示例1

输入

复制

2
2 3
4 6

输出

复制

-1
1

说明

对于第一次询问，唯二的两种放入方式为  或者 ，但是都不满足条件，所以输出 。 
对于第二次询问，可以分组为 ，此时满足条件。