import java.util.*;
import java.math.*;
public class PrimeCompositeGame {
boolean [] primes;
int [] dif;
public int theOutcome(int N, int K) {
if(N<3)return 0;
sieve();//to get the primes
difBuild();//to build all the differences between index and the closest smaller prime
int l = firstlose(K);//get the first integer the difference between it and the closest smaller prime is bigger than K
if(l==-1||l>N){// you win
return win(N,K);
}else{//you lose
return lose(N,K);
}
}
private int lose(int n,int k) {
int turns=0;
while(true){
if(dif[n]==0&&dif[n-1]>k-1)return -1*turns;//if you can\'t move
if(dif[n]>k)return -1*turns;//if you can\'t move
if(dif[n]==0)n--;//if you started at a prime
n=n-dif[n];//get the closest prime
for (int i = 1; i <= k; i++) {//search if there exist a losing state in range
if(n-i<0)continue;
if(dif[n-i]>k)return -1*(turns+2);
}
for (int i = 0; i < k; i++) {//get the smallest integer you can get
if(n-k+i<0)continue;
if(!primes[n-k+i]){n=n-k+i;break;}
}
turns+=2;
}
}
private int win(int n,int k) {
int turns=0;
while(true){
if(n-3<=k){//no more moves
return turns+1;
}
turns+=2;
for (int i = 0; i < k; i++) {//get the smallest prime within range then remove one
if(n-k+i<0)continue;
if(primes[n-k+i]){n=n-k-1+i;break;}
}
}
}
private void sieve() {
// TODO Auto-generated method stub
primes=new boolean[500000];
Arrays.fill(primes, true);
primes[0]=false;
primes[1]=false;
for (int i = 2; i < primes.length; i++) {
if(primes[2]){
for (int j = i+i; j < primes.length; j+=i) {
primes[j]=false;
}
}
}
}
private void difBuild(){
dif=new int[500000];
for (int i = 2; i < dif.length; i++) {
if(primes[i])dif[i]=0;
else dif[i]=dif[i-1]+1;
}
}
private int firstlose(int k){
for (int i = 4; i < dif.length; i++) {
if(dif[i]>k)return i;
}
return -1;
}
}