# Prime Sum PRIMESM Codechef Solution

## Prime Sum PRIMESM Codechef Solution

Given two integers A and B. Let P denote a sequence of N prime numbers such that the sum of the sequence is A. Let Q denote a sequence of M prime numbers such that the sum of the sequence is B. Let X denote the maximum absolute difference between Pi and Qj among all valid pairs (i,j) such that (1≤i≤N) and (1≤j≤M). Find the minimum possible value of X over all possible sequences P and Q.

More formally, for all possible sequences P and Q, find the minimum value of max(|Pi−Qj|), where (1≤i≤N) and (1≤j≤M). Print −1 if any one of the sequences cannot be formed.

Note that, |X| denotes the absolute value of a number X. For example, |−4|=4 and |7|=7.

Input Format
First line will contain T, the number of test cases. Then the test cases follow.
Each test case contains two integers A and B.

Output Format
For each test case, find the minimum possible value of the maximum absolute difference between Pi and Qj for (1≤i≤N) and (1≤j≤M). If any of the sequences can not be formed, print −1 instead.

Constraints

• 1≤T≤105
• 1≤A≤1018
• 1≤B≤1018

Sample Input 1
2
3 6
3 2

Sample Output 1
0
1

Explanation

• Test case 1: Let P={3} and Q={3,3}.
The maximum absolute difference is 0. It can be shown that the maximum absolute difference can not be less than 0.
• Test case 2: The only possible sequences are P={3} and Q={2}.
The maximum absolute difference is 1. It can be shown that the maximum absolute difference can not be less than 1.

### SOLUTION

Program: Prime Sum PRIMESM Codechef Solution in Python

``````def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)

for _ in range(int(input())):
a,b = map(int,input().split(" "))
if a==1 or b==1:
print(-1)
else:
t = gcd(a,b)
if t != 1:
print(0)
else:
print(1)``````

Program: Prime Sum PRIMESM Codechef Solution in C++

``````#include<bits/stdc++.h>
using namespace std;
#define f for(ll i=0;i<n;i++)
typedef long long ll;
int main(){
ll t;
cin>>t;
while(t--){
ll x,y;
cin>>x>>y;
if(x==1 || y==1)
cout<<-1<<endl;
else if(__gcd(x,y)!=1)
cout<<0<<endl;
else
cout<<1<<endl;
}
}``````

Program: Prime Sum PRIMESM Codechef Solution in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
static long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a%b);
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
long a = sc.nextLong();
long b = sc.nextLong();
if (a==1 || b==1){
System.out.println(-1);
}
else if (gcd(a,b)==1){
System.out.println(1);
}
else
System.out.println(0);
}
}
}``````

Related: