Biến đổi số

View as PDF

Submit solution

Points: 1.67 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Từ một số tự nhiên ~X~, ta có thể thực hiện ~2~ thao tác sau:

  • Tăng ~X~ lên ~1~ đơn vị
  • Hoán vị các chữ số của ~X~ (chữ số đầu tiên phải khác ~0)~

Hỏi từ ~X = 1~, chúng ta cần ít nhất bao nhiêu thao tác để ~X = N~

Input

  • Dòng ~1~: Chứa số nguyên ~T~ là số test
  • ~T~ dòng tiếp theo, mỗi dòng chứa một số tự nhiên ~N~

Output

Gồm ~T~ dòng, dòng thứ ~i~ in ra một số tự nhiên duy nhất là số thao tác ít nhất của test thứ ~i~

Giới hạn

  • ~T \le 100~
  • ~30\%~ số test có ~N \le 10^{5}~
  • ~70\%~ số test còn lại có ~N \le 10^{18}~

Sample Input

1
21

Sample Output

12

Note

~1 \rightarrow~ ~2 \rightarrow~ ~3 \rightarrow~ ~4 \rightarrow~ ~5 \rightarrow~ ~6 \rightarrow~ ~7 \rightarrow~ ~8 \rightarrow~ ~9 \rightarrow~ ~10 \rightarrow~ ~11 \rightarrow~ ~12 \rightarrow~ ~21~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.