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