Маленький Т и маленький S определили номер комнаты главного зала в десятичной системе счисления как $n$. Маленький Т дает следующее определение «аккуратного» представления номера комнаты: для целых чисел $b, p \ge 2$, если $b$-ичная запись номера комнаты $n$ состоит из нескольких сегментов длины $p$, каждый из которых представляет собой повторение одной и той же цифры, то $(b, p)$ считается аккуратным представлением.
Формально, пусть $b$-ичная запись числа $n$ имеет вид $d_{k-1}d_{k-2} \dots d_1d_0$. Если существует целое число $c$ такое, что общее количество разрядов $k = cp$, и для всех $0 \le i < c$ выполняется условие $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, то $(b, p)$ является аккуратным представлением.
Например, если номер комнаты $2233$ или $3355$, то $(10, 2)$ является аккуратным представлением; если номер комнаты $1111$, то $(10, 2)$ и $(10, 4)$ — два различных аккуратных представления; если номер комнаты $6737151$ (в шестнадцатеричной системе это $66CCFF$), то $(16, 2)$ является аккуратным представлением.
Чтобы успешно получить входной билет, вам нужно ответить на вопрос маленького Т и маленького S: сколько всего существует аккуратных представлений для номера комнаты главного зала?
Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 10^3$), количество наборов данных. Для каждого набора данных: * Первая строка содержит целое число $n$ ($1 \le n \le 10^{12}$), представляющее номер комнаты главного зала.
Гарантируется, что сумма $n$ по всем наборам данных не превышает $10^{12}$.
Для каждого набора данных выведите в одной строке одно неотрицательное целое число — ответ на задачу.
Примеры
Входные данные 1
10 1 2 115 1111 2233 3355 191970 6737151 102934760424 618111100000
Выходные данные 1
0 0 2 4 5 5 24 9 17 144
Примечание
Для третьего набора данных $115 = (55)_{22} = (11)_{114}$, поэтому все аккуратные представления: $(22, 2)$ и $(114, 2)$.
Для четвертого набора данных все аккуратные представления: $(10, 2), (10, 4), (100, 2), (1110, 2)$.