# Prime Sum Codechef Solution | C++, Java, Python | APRIL CHALLENGE Share:

Prime Sum Codechef Solution

Given two integers AA and BB.

• Let PP denote a sequence of NN prime numbers such that the sum of the sequence is AA.
• Let QQ denote a sequence of MM prime numbers such that the sum of the sequence is BB.

Let XX denote the maximum absolute difference between PiPi and QjQj among all valid pairs (i,j)(i,j) such that (1≤i≤N)(1≤i≤N) and (1≤j≤M)(1≤j≤M). Find the minimum possible value of XX over all possible sequences PP and QQ.

More formally, for all possible sequences PP and QQ, find the minimum value of max(|Pi−Qj|)max(|Pi−Qj|), where (1≤i≤N)(1≤i≤N) and (1≤j≤M)(1≤j≤M).

Print −1−1 if any one of the sequences cannot be formed.

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

### Input Format

• First line will contain TT, the number of test cases. Then the test cases follow.
• Each test case contains two integers AA and BB.

### Output Format

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

### Constraints

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

### Sample Input 1

``````2
3 6
3 2
``````

### Sample Output 1

``````0
1
``````

### Explanation

Test case 11: Let P={3}P={3} and Q={3,3}Q={3,3}.
The maximum absolute difference is 00. It can be shown that the maximum absolute difference can not be less than 00.

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