Với mọi số nguyên dương \(x\), hàm \(f(x)\) được định nghĩa như sau:

• Nếu \(x\) có bất kỳ chữ số nào khác \(0\) và \(1\), với mỗi chữ số của \(x\), đổi chữ số đó thành \(1\) nếu nó lẻ, hoặc thành \(0\) nếu không, rồi trả về \(x\).
• Nếu không, trả về \(x-1\).

Cho một giá trị \(x\) (\(1\leq x<10^{2\cdot 10^5}\)), hãy tìm số lần cần áp dụng \(f\) lên \(x\) để \(x\) trở thành \(0\). Vì số này có thể rất lớn, hãy in phần dư của nó khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10^5\)), số lượng bộ test độc lập.

\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(x\) chỉ gồm các chữ số từ 0 đến 9 và không có chữ số \(0\) ở đầu.

Đảm bảo tổng số chữ số trong tất cả các số nguyên đầu vào không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng riêng phần dư của số lần cần áp dụng hàm khi chia cho \(10^9+7\).

Ví dụ

2
24680
210

1
4

1
1234567890123456789012345678901234567890

511620083

Phân nhóm

• Dữ liệu 3-5: \(T\le 2000\), \(x<10^9\).
• Dữ liệu 6-7: \(x<10^{18}\).
• Dữ liệu 8-9: \(x<10^{60}\).
• Dữ liệu 10-12: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Strange Function. Tác giả: Aidan Bai.
https://usaco.org/index.php?page=viewproblem2&cpid=1588