Farmer Feb

Problem Statement

Farmer Feb has three fields with potatoes planted in them. He harvested x potatoes from the first field, ypotatoes from the second field and is yet to harvest potatoes from the third field. Feb is very superstitious and believes that if the sum of potatoes he harvests from the three fields is a prime number (http://en.wikipedia.org/wiki/Prime_number), he'll make a huge profit. Please help him by calculating for him the minimum number of potatoes that if harvested from the third field will make the sum of potatoes prime. At least one potato should be harvested from the third field.

Input

The first line of the input contains an integer T denoting the number of test cases. Each of the next T lines contain 2 integers separated by single space: x and y.

Output

For each test case, output a single line containing the answer.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ x ≤ 1000
• 1 ≤ y ≤ 1000

Example

Input:
2
1 3
4 3

Output:
1
4

Explanation

In example case 1: the farmer harvested a potato from the first field and 3 potatoes from the second field. The sum is 4. If he is able to harvest a potato from the third field, that will make the sum 5, which is prime. Hence the answer is 1(he needs one more potato to make the sum of harvested potatoes prime.)

Problem Link : potatoes

The idea:  The problem demands the next prime number after the sum of x+y . Thus we can simply go for a loop with prime checking.For prime checking we need see if there  should be no factors from 2 to sqrt(number).But sqrt is an expensive operation we can use i*i<=number to get the same effect.

The Code:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
6. bool isPrime(int res)
7. {
8. bool check=true;
9. for(int i=2;i*i<=res;i++)
10. {
11. if(res%i==0)
12. {
13. check=false;
14. break;
15. }
16. }
17. return check;
18. }
20. int main()
21. {
22. int T;
23. scanf("%d",&T);
24. while(T--)
25. {
26. int x,y;
27. scanf("%d %d",&x,&y);
28. int answer=0;
29. for(int i=1;;i++)
30. {
31. int res=x+y+i;
32. if(isPrime(res))
33. {
34. answer=i;
35. break;
36. }
37. }
39. cout<<answer<<endl;
41. }
42. return 0;
43. }