문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

• 입력: 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
• 출력: 각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

재용이..?

뭔가 문제가 장황한데 결국 요약하면

a^b개의 태스크를 10대의 컴퓨터가 번갈아 수행한다고 할 때, 마지막 태스크를 수행하는 건 몇 번 컴퓨터인지 구하는 문제이다.

b의 최댓값이 꽤 크므로 제곱값을 모두 구하두록 두고싶지 않다는 생각이 제일 먼저 들었다.

다행히도 어떤 수를 거듭제곱하면 1의 자리수는 반복될 수밖에 없다.

예컨대 9를 거듭제곱하면 9 -> 81 -> 729 -> 6561-> 59049 -> ......1 -> .......9 로, [9,1]의 패턴이 생긴다.