키 저장소

Karl은 키 저장소 서비스를 개발하고 있다. 각 사용자는 양의 정수 키를 하나씩 가진다.

Karl은 키를 평문으로 저장하는 것이 좋지 않다는 것을 안다. 그래서 키 자체를 저장하는 대신 키의 지문을 저장하기로 했다. 그런데 기존의 지문 알고리즘을 사용하는 것은 너무 지루해 보였기 때문에 직접 알고리즘을 만들었다.

Karl의 지문은 다음과 같은 과정으로 계산한다. 주어진 정수를 2로 나누고, 그 결과를 3으로 나누고, 다시 그 결과를 4로 나누는 식으로 결과가 0이 될 때까지 계속한다. 나눗셈은 매번 정수 나눗셈이다. 지문은 이 나눗셈들의 나머지로 이루어진 중복집합으로 정의한다.

예를 들어 키 11에 Karl의 지문 알고리즘을 적용하면 다음과 같다. 11을 2로 나누면 나머지가 1이고 결과가 5이며, 5를 3으로 나누면 나머지가 2이고 결과가 1이고, 1을 4로 나누면 나머지가 1이고 결과가 0이다. 따라서 키 11은 나머지 수열 $[1, 2, 1]$을 만들고 지문 중복집합 $\{1, 1, 2\}$를 가진다.

Ksenia는 Karl의 지문 알고리즘이 그다지 좋지 않다는 것을 증명하려고 한다. 예를 들어 그녀는 키 178800과 123456이 모두 지문 $\{0, 0, 0, 0, 2, 3, 3, 4\}$를 만든다는 사실을 알아냈다. 따라서 사용자들은 123456처럼 흔히 쓰이고 추측하기 쉬운 키와 지문이 충돌할 위험이 있다.

Ksenia는 자신의 주장을 더 설득력 있게 만들고 싶다. 그녀는 흔히 쓰이는 키들의 목록에 있는 각 키와 같은 지문을 가지는 다른 키의 개수를 계산하려고 한다. 당신은 그녀를 도와야 한다.

첫째 줄에 정수 $t$ ($1 \le t \le 50\,000$)가 주어진다. 이는 살펴볼 흔히 쓰이는 키의 개수이다. 다음 $t$개 줄에 각각 정수 $k_i$ ($1 \le k_i \le 10^{18}$)가 하나씩 주어진다. 이는 키 자체이다.

각 키에 대해 같은 지문을 가지는 다른 키의 개수를 한 줄에 하나씩 출력한다.

11과 같은 지문을 가지는 다른 키는 15이다. 15는 나머지 수열 $[1, 1, 2]$를 만든다. 따라서 두 수는 모두 지문 중복집합 $\{1, 1, 2\}$를 가진다.