Statement

Martha has a permutation P_0, P_1, …, P_N-1 of the numbers 1 to N. Unfortunately, it is quite scrambled, so she wants to sort it, i.e. get the permutation 1, 2, …, N. The Magic Store sells N types of wands. Through the i-th (1 ≤ i ≤ N) wand, you can swap the a-th and b-th elements of a permutation if and only if i divides P_a - P_b. Martha has money for buying only one wand. For every i (1 ≤ i ≤ N), she wonders whether she would be able to sort the permutation by buying the i-th wand, and what would be the minimum number of swaps needed in that case.