小F在寻宝的过程中无意间发现了一个藏宝图，他非常兴奋，但是这张图很复杂，他索性将这个难题交给你，
你发现这个藏宝图是由 1 ~ n ， n 个节点组成的，且只有当两个节点编号的最大公约数为质数(包括 1 ）才会在两条节点间连一条长度为 1 的边,
那么现在你只需要找到到达宝藏的最短距离就行，你们目前处于 x 节点，而宝藏位于 y 节点
第一行包含一个整数 T ，表示测试用例的组数 ( 1<=T<=1000 )
对于每个测试用例：
第一行输入一个正整数 n 表示节点数 ( 1<=n<=10^9 )
第二行输入两个正整数 x 和 y 表示当前的位置和宝藏的位置 ( 1<=x<=n，1<=y<=n ， )
仅输出一行，包含一个整数，表示
到达宝藏的最短距离
如果到达不了输出 -1
输入样例
1 10 6 9
输出样例
1
注意: （1）每个节点都可以与1相连，（2） x,y 的最大公约数是质数就可以直接相连，（3） x,y 也可以相等