Mô tả bài toán

Một số được gọi là "binary decimal" nếu đó là một số nguyên dương và tất cả các chữ số trong biểu diễn dạng thập phân của nó chỉ là 0 hoặc 1. Ví dụ: 1010111 là một binary decimal, trong khi 10201 và 787788 thì không phải.

Cho một số nguyên n, hãy biểu diễn n dưới dạng tổng của một số (có thể lặp) các binary decimals. Hãy tính số lượng nhỏ nhất các binary decimals cần để biểu diễn n.

Ràng buộc

Số lượng test t: 1 ≤ t ≤ 1000

Với mỗi test, 1 ≤ n ≤ 10^9

Đầu vào

Dòng đầu chứa một số nguyên t — số lượng test. Mỗi test gồm một dòng chứa một số nguyên n.

Đầu ra

Với mỗi test, in ra một dòng chứa một số nguyên — số lượng nhỏ nhất các binary decimals cần để biểu diễn n.

Ví dụ

Input

3
121
5
1000000000

Output

2
5
1

Ghi chú

Trong test 1: 121 có thể được biểu diễn như 110 + 11 hoặc 111 + 10.

Trong test 2: 5 = 1 + 1 + 1 + 1 + 1.

Trong test 3: 1000000000 tự thân là một binary decimal nên đáp án là 1.