소 T와 소 S가 정한 주회장 방 번호는 십진수로 $n$입니다. 소 T는 '정갈한' 방 번호 표기 방식에 대해 다음과 같이 정의했습니다. 정수 $b, p \ge 2$에 대하여, 방 번호 $n$의 $b$진법 표기가 정확히 길이가 $p$인 여러 구간의 동일한 숫자로 이어져 있다면, $(b, p)$를 정갈한 표기 방식이라고 합니다.

형식적으로, $n$의 $b$진법 표기를 $d_{k-1}d_{k-2} \dots d_1d_0$이라 할 때, 총 자릿수 $k = cp$를 만족하는 양의 정수 $c$가 존재하고, 모든 $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(16진법으로 66CCFF)이라면 $(16, 2)$는 정갈한 표기 방식입니다.

입장권을 얻기 위해 소 T와 소 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)$입니다.