Tiểu T và Tiểu S đã xác định số phòng của hội trường chính trong hệ thập phân là $n$. Tiểu T đưa ra định nghĩa về cách biểu diễn số phòng "gọn gàng" như sau: Với các số nguyên dương $b, p \ge 2$, nếu biểu diễn cơ số $b$ của số phòng $n$ được ghép lại từ nhiều đoạn có độ dài $p$ với các chữ số giống nhau, thì $(b, p)$ được coi là một cách biểu diễn gọn gàng.

Một cách hình thức, giả sử biểu diễn cơ số $b$ của $n$ là $d_{k-1}d_{k-2} \dots d_1d_0$. Nếu tồn tại số nguyên dương $c$ sao cho tổng số chữ số $k = cp$, và với mọi $0 \le i < c$, ta luôn có $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, thì $(b, p)$ là một cách biểu diễn gọn gàng.

Ví dụ, nếu số phòng là $2233$ hoặc $3355$, thì $(10, 2)$ là một cách biểu diễn gọn gàng; nếu số phòng là $1111$, thì $(10, 2)$ và $(10, 4)$ là hai cách biểu diễn gọn gàng khác nhau; nếu số phòng là $6737151$ (biểu diễn trong hệ thập lục phân là $66CCFF$), thì $(16, 2)$ là một cách biểu diễn gọn gàng.

Để giành được vé vào cửa, bạn cần trả lời câu hỏi của Tiểu T và Tiểu S: Có tổng cộng bao nhiêu cách biểu diễn gọn gàng cho số phòng của hội trường chính?

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên dương $T$ ($1 \le T \le 10^3$), biểu thị số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu: * Dòng đầu tiên chứa một số nguyên dương $n$ ($1 \le n \le 10^{12}$), biểu thị số phòng của hội trường chính.

Đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^{12}$.

Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên không âm, biểu thị đáp án.

Ví dụ

Dữ liệu vào 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

Dữ liệu ra 1

0
0
2
4
5
5
24
9
17
144

Ghi chú

Đối với bộ dữ liệu thứ ba, $115 = (55)_{22} = (11)_{114}$, do đó tất cả các cách biểu diễn gọn gàng là $(22, 2), (114, 2)$.

Đối với bộ dữ liệu thứ tư, tất cả các cách biểu diễn gọn gàng là $(10, 2), (10, 4), (100, 2), (1110, 2)$.