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

• (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.

Input

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^6.

Output

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

Example

Input
4
1
3
5
7

Output
0
2
3
4