헌내기 현철

불과 몇 달 전만 해도 새내기였던 현철이는 $22$학번을 이십이학번이 아닌 이이학번으로 읽는다는 것을 신기하게 생각했다. 그런데, 이제 $23$학번이 들어온다는 소식에 현철이는 큰 충격에 빠졌다. 그래서 이삼학번 새내기들이 이십삼학번으로 학번을 읽는 것을 미리 방지하고자 하나의 수식을 생각했다.

$N= a\_0 + a\_1 × 10 + a\_2 × 10^2 + \cdots + a\_i × 10^i + \cdots (0 \le a\_i \le 9, a\_i \in \mathbb{Z})$

만약 $N=23$이면 $a\_0 = 3$이고, $a\_1 = 2$ 이며, $2 \le i$ 일 때, $a\_i = 0$ 이다.

위의 수식으로 현철이는 후배들에게 $23$ 학번을 이십삼이 아닌 이삼학번으로 읽는다는 것을 설명할 생각에 신이 났다. 현철이는 신나게 수식을 보다가 재미난 생각이 떠올랐다. 저 수식에 $N$ 대신 $A^k$ 을 넣는 것이다. 그런데, 아무 수를 $A$에 넣으면 재미가 없을 것 같다고 느낀 현철이는 $10^{18}$ 이하의 양의 정수만 들어가게 하였다. 또 다시 $k$에 아무 숫자나 넣는 것보다는 $B^C$을 넣는 것이 재밌겠다고 생각했다. $B$ 또한 $A$와 마찬가지로 $10^{18}$이하의 양의 정수만 들어가게 하였다. 그 후, 현철이는 다음과 같은 질문을 하게 된다.

• 현철: 임의의 $C$ 에 대해 그때의 $a\_i$값을 구할 수 있을까?

자 여러분은 이제 현철이의 질문에 대한 답을 구해보자

$N$에 위의 숫자를 넣으면 다음과 같은 수식이 된다.

$A^{B^C} = a\_0 + a\_1 × 10 + a\_2 × 10^2 + \cdots + a\_i × 10^i + \cdots$

첫 번째 줄에는 총 테스트케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 1\\,000$)를 입력받는다.

두 번째 줄부터 $T+1$ 번째 줄까지 각 줄에 걸쳐 각 테스트 케이스에 해당하는 네 개의 양의 정수 $A$, $B$ ($1 \le A, B \le 10^{18}$), $i$ ($1 \le i \le 6$) 그리고 $C$ ($1 \le C \le 10^{1000}-1$) 가 공백으로 구분되어 주어진다.

첫 번째 줄부터 $T$ 번째 줄까지 입력받은 순서에 따라 각 테스트케이스 별 정답을 출력한다.