module m implicit none integer(kind=8)::p=100000009 contains subroutine solve(seed,n,k,b) implicit none integer(kind=8)::seed,n,k,b,x(0:10000),div(3),pow(3),cnt(0:70) integer(kind=8)::ans integer(kind=8)::i,j,r,tmp,tmp1,tmp2,tmp3,gen ans=1000000 x(0)=seed do i=0,n-1 x(i+1)=next(x(i)) end do call factor(b,div,gen,pow) do i=1,gen-1 do j=1,size(cnt) cnt(j-1)=0 end do do j=0,n tmp=x(j) r=0 do while(tmp>1.and.mod(tmp,div(i))==0) tmp=tmp/div(i) r=r+1 end do cnt(r)=cnt(r)+1 end do r=k tmp=0 do j=0,size(cnt)-1 if(r-cnt(j)<=0)then tmp=tmp+r*j r=0 exit else tmp=tmp+cnt(j)*j r=r-cnt(j) end if end do ans=min(ans,tmp/pow(i)) end do print*,ans end subroutine subroutine factor(n,div,gen,pow) integer(kind=8),intent(in)::n integer(kind=8)::gen,tmp,div(*),pow(*),r,i,j gen=1 tmp=n do i=2,tmp r=0 do while(mod(tmp,i)==0) tmp=tmp/i r=r+1 end do if(r>0)then div(gen)=i pow(gen)=r gen=gen+1 end if if(i*i>=tmp)exit end do if(tmp>1)then div(gen)=tmp pow(gen)=1 gen=gen+1 end if end subroutine integer(kind=8) function next(x) integer(kind=8)::x next=1+mod(mod(x*x,p)+mod(x*12345,p),p) end function end module program main use m implicit none integer(kind=8)::q,seed,n,k,b integer::i,j,x,y,z,r read*,q do i=1,q read(*,*)seed,n,k,b call solve(seed,n,k,b) end do end program