The Efficient Steps#12465
You are given a positive integer . In one move, you can subtract either or from .
Your goal is to reduce to exactly using the minimum number of moves possible.
(Note: The value of must never become negative).
The first line consists of a single integer (1 \le T \le 1000)the number of testcases.
Each testcase consists of a single integer (2 \le N \le 10^9).
For each test case, output a single integer: the minimum number of moves required. If it is impossible to reach exactly 0, output -1.
Example 1
N=2 : Subtract once. Count = .
N=4 : Subtract 2 twice (4 \to 2 \to 0). Count = .
N=5 : Subtract 3 then 2 (5 \to 2 \to 0). Count = .
N=7 : Best path: 7 \xrightarrow{-3} 4 \xrightarrow{-2} 2 \xrightarrow{-2} 0. Count = .
Subtask ( points): The sum of over all test cases does not exceed 10^5.
Subtask 2 ( points): Original constraints.