Cho số nguyên dương ~n~. Với mỗi thao tác, ta trừ ~n~ cho tổng các chữ số của ~n~. Hãy đếm số thao tác để ~n = 0~. Cần xử lý ~q~ số ~n~ như vậy.

Yêu cầu: Với mỗi số ~n~, tính số bước cần thiết để đưa ~n~ về ~0~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~q~ (~1 \le q \le 10^5~).
• Dòng tiếp theo gồm ~q~ số nguyên dương ~n~ tương ứng với ~q~ bộ dữ liệu (~1 \le n \le 10^{18}~).

Output

• Gồm ~q~ số nguyên trên một dòng, số thứ ~i~ là kết quả cho bộ dữ liệu thứ ~i~.

Sample Input 1

3
18 19 20

Sample Output 1

2 2 3