Given -
There are N cities we can visit two i and j cities such that abs(i-j)) is factor of N and abs(i-j)>1.We can perform following operation
choose a random number i and find all j which satisfy N%|i-j|==0 ie. all cities connected to i can be visited in one go.
Find minimum number of operation so that we can visit all cities.
example-
N=4
ans=2
explaination:- 1->3 and 2->4
N=5
ans=5
explaination:- as 5 is prime hence 1,2,3,4,5 are visited seprately
constraints=>N<1010