Given T test cases T<=100000 In each test case given a positive integer A.A<=100000 You can perform any of the following steps(one of them):.
1) decrement A by 1.
2) increment A by 1.
3) divide A by one of it's prime factor.
Find minimum number of steps to reduce A to 1. 1) it is best to divide by max prime factor or finding nearest prime number whichever is minimum. This is codeforces problem but I can't find it