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~