Pair Transformation

Time limit1sMemory limit256 MB

Summary

From (1,1), add one component to the other or swap them, and report the fewest steps that put N in the pair for each query.

Level: Medium7 of 10
Topics: Number theory, BFS, Brute force
Solved: No attempts yet

Problem

Given a pair $(a, b)$ of two positive integers, you may apply one of the following three transformations to build a new pair.

$(a, b) \to (a, a + b)$
$(a, b) \to (a + b, b)$
$(a, b) \to (b, a)$

Start from the pair $(1, 1)$ and build a pair that holds $N$ . A pair holds $N$ when at least one of its two components equals $N$ . Find the fewest transformations that do it.

Input

The first line has the number of tests $T$ . $(1 \le T \le 20)$

Each of the next $T$ lines has one integer $N$ . $(1 \le N \le 10^6)$

Output

For each test, print the fewest transformations on its own line.

Hint

For $N = 1$ the starting pair already holds $1$ , so no transformation is needed.

For $N = 3$ , two transformations are enough: $(1, 1) \to (2, 1) \to (3, 1)$ .

For $N = 5$ , three are enough: $(1, 1) \to (2, 1) \to (2, 3) \to (2, 5)$ .

For $N = 7$ , four are enough: $(1, 1) \to (2, 1) \to (2, 3) \to (2, 5) \to (2, 7)$ .

Examples4

Example 1
Input
```
4
1
3
5
7
```
Expected output
```
0
2
3
4
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
3
2
4
6
```
Expected output
```
1
3
5
```

Example 4

Input

Expected output