Hàm Kỳ Lạ

Cho số nguyên dương $x$, định nghĩa hàm $f(x)$ như sau:

• Nếu $x$ có ít nhất một chữ số không phải $0$ hoặc $1$: với mỗi chữ số của $x$, đặt nó thành $1$ nếu lẻ, $0$ nếu chẵn, rồi trả về $x$.
• Ngược lại (tất cả chữ số đều là $0$ hoặc $1$): trả về $x-1$.

Tìm số lần cần áp dụng $f$ để $x$ trở thành $0$. Kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le {10}^5$)
• $T$ dòng tiếp theo: Mỗi dòng chứa số nguyên dương $x$ (không có số $0$ đứng đầu, $1\le x<{10}^{2\times {10}^5}$)

Tổng số chữ số trên tất cả các bộ test không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi bộ test, in ra số lần áp dụng hàm $f$ modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le {10}^5$
• $1\le x<{10}^{2\times {10}^5}$
• Tổng chữ số $\le {10}^6$

Ví dụ

Ghi chú

• Test 3-5: $T\le 2000$, $x<{10}^9$
• Test 6-7: $x<{10}^{18}$
• Test 8-9: $x<{10}^{60}$
• Test 10-12: Không ràng buộc bổ sung