27299번 - 헌내기 현철

문제

불과 몇 달 전만 해도 새내기였던 현철이는 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$ 번째 줄까지 입력받은 순서에 따라 각 테스트케이스 별 정답을 출력한다.

제한

힌트