Biến đổi cặp số

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 6.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSPC 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Please read the guidelines before commenting.


There are no comments at the moment.