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 \leq N \leq 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.

Sample Input

4
1
3
5
7

Sample Output

0
2
3
4