Kata

Task

You are given 3 positive integers a, b, k. Using one operation you can change a or b (but not both) by k (add or subtract are all ok). Count the minimum number of operations needed to make a, b > 0 and gcd(a, b) > 1.

You have to write a function gcd_neq_one() which receives 3 positive integers a, b, k and return a positive integer: the solution of the problem.

Examples

Input: a=5, b=9, k=1

Output: Doing a single operation of (+k) to a (5 + 1 * 1) results in gcd(6,9) = 3

Minimum moves required: 1 operation

​

Input: a=2, b=3, k=6

Output: Doing 3 operations of (+k) to a (2 + 3 * 6) and 2 operations of (+k) to b (3 + 2 * 6) results in gcd(20,15) = 5

Minimum moves required: 5 operations

---

You can read the original, Vietnamese statement at my page (TLEoj): https://tleoj.edu.vn/problem/21c