수 쌍 변환

양의 정수 두 개로 이루어진 순서쌍 $(a, b)$에 다음 세 가지 변환 중 하나를 적용해서 새로운 순서쌍을 만들 수 있다.

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

순서쌍 $(1, 1)$에서 시작해서 $N$이 들어 있는 순서쌍을 만들려고 한다. 두 성분 중 적어도 하나가 $N$과 같으면 그 순서쌍은 $N$을 담고 있다. 변환을 가장 적게 쓰는 방법의 변환 횟수를 구하여라.

첫째 줄에 테스트 개수 $T$가 주어진다. $(1 \le T \le 20)$

다음 $T$개의 줄에 정수 $N$이 한 줄에 하나씩 주어진다. $(1 \le N \le 10^6)$

각 테스트마다 최소 변환 횟수를 한 줄에 하나씩 출력한다.

$N = 1$이면 시작 순서쌍이 이미 $1$을 담고 있어서 변환이 필요 없다.

$N = 3$은 $(1, 1) \to (2, 1) \to (3, 1)$로 두 번 만에 만든다.

$N = 5$는 $(1, 1) \to (2, 1) \to (2, 3) \to (2, 5)$로 세 번 만에 만든다.

$N = 7$은 $(1, 1) \to (2, 1) \to (2, 3) \to (2, 5) \to (2, 7)$로 네 번 만에 만든다.