(numberna.*)

Trên mặt bảng ghi số 1. Mỗi một lần biến đổi, Bờm thực hiện một trong hai phép toán sau đây đối với số viết trên bảng: Hoặc là cộng thêm nó với 1, hoặc là đổi chỗ các chữ số của nó (Nhưng không bao giờ có số 0 ở vị trí thứ nhất tính từ trái sang phải). Sau đó xóa số đang có trên bảng và viết kết quả thu được lên bảng.

Yêu cầu: Cho trước một số nguyên dương, hãy tính xem sau ít nhất bao nhiêu lần biến đổi bắt đầu từ số 1 Bờm sẽ thu được số đã cho.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(t\) (\(1\ \leq \ t\ < \ 10^{4}\)) là số lượng test.

• Dòng thứ \(i\) trong \(t\) dòng tiếp theo chứa số nguyên \(n_{i}\ (2\ \leq \ n_{i}\ < \ 10^{9},\ 1\ \leq \ i\ \leq \ t)\).

Kết quả: Ghi \(t\ \)số, mỗi số trên một dòng, trong đó số trên dòng thứ \(i\) là số lần biến đổi ít nhất cần thực hiện để thu được trên bảng số \(n_{i}\).

Ví dụ:

Hạn chế: 25% số test có \(2\ \leq \ n_{i}\ \leq \ 100\) với mọi \(i\).

25% số test có \(t\ = 1,\ 100\ \leq \ n_{1}\ < \ 10^{4}\).

15% số test có \(t\ > \ 1,\ 100\ \leq \ n_{i}\ < \ 10^{4}\) với mọi \(i\).

35% số test có \(10^{4}\ \leq \ n_{i}\ < \ 10^{9}\) với mọi \(i\).