Từ cặp số (a, b) gồm 2 số nguyên dương, có thể sử dụng 1 trong 3 phép biến đổi sau để tạo ra cặp số mới </p>

• (a,b) → (a, a+b) 
• (a,b) → (a+b, b) 
• (a,b) → (b,a) 

Bắt đầu từ cặp số (1, 1) hãy dùng ít phép biến đổi nhất để tạo ra một cặp số có chứa số N.

입력 형식

Dòng đầu chứa số test T. Tiếp theo là T test, mỗi test chứa một số 1 ≤ N ≤ 10⁶.

출력 형식

Ứng với mỗi test, in ra trên một dòng số bước biến đổi ít nhất.

예제 입력

4
1
3
5
7

예제 출력

0
2
3
4

힌트

• (1 1)
• (1 1) → (2 1) → (3 1) 
• (1 1) → (2 1) → (2 3) → (2 5) 
• (1 1) → (2 1) → (2 3) → (2 5) → (2 7)