题意：
思路：
极限步数大概不会超过30
1 const max=100000; 2 var dp:array[1..max,0..2]of longint; 3 eul:array[1..max]of longint; 4 cas,v,n,k,i,ans,j:longint; 5 6 function min(x,y:longint):longint; 7 begin 8 if x<y then exit(x); 9 exit(y); 10 end; 11 12 function euler(x:longint):longint; 13 var tmp,i:longint; 14 begin 15 if x<=max then exit(eul[x]); 16 euler:=x; tmp:=trunc(sqrt(x)); 17 for i:=2 to tmp do 18 if x mod i=0 then 19 begin 20 while x mod i=0 do x:=x div i; 21 euler:=euler div i*(i-1); 22 end; 23 if x>1 then euler:=euler div x*(x-1); 24 end; 25 26 function clac(n,k:longint):longint; 27 begin 28 if n<=max then exit(dp[n,k]); 29 clac:=clac(euler(n),k)+1; 30 if k>0 then clac:=min(clac,clac((n>>1)+1,k-1)+1); 31 end; 32 33 begin 34 assign(input,'func.in'); reset(input); 35 assign(output,'func.out'); rewrite(output); 36 readln(cas); 37 for i:=1 to max do eul[i]:=i; 38 for i:=2 to max do 39 begin 40 if eul[i]=i then 41 for j:=1 to max div i do eul[i*j]:=eul[i*j] div i*(i-1); 42 dp[i,0]:=dp[eul[i],0]+1; 43 dp[i,1]:=min(dp[eul[i],1],dp[(i>>1)+1,0])+1; 44 dp[i,2]:=min(dp[eul[i],2],dp[(i>>1)+1,1])+1; 45 end; 46 47 for v:=1 to cas do 48 begin 49 readln(n,k); 50 ans:=clac(n,0); 51 if k>0 then ans:=min(ans,clac(n,1)); 52 if k>1 then ans:=min(ans,clac(n,2)); 53 writeln(ans); 54 end; 55 close(input); 56 close(output); 57 end.