Submit solution
Points:
0.50 (partial)
Time limit:
6.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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
Comments