#105차례로 돌아가며 작업 맡기기

한 회사에는 컴퓨터 10대가 있고, 직원들은 각 컴퓨터에 1번부터 10번까지 번호를 매겨 작업을 맡기기로 했다. 작업을 맡기는 순서는 다음과 같다.

1번 작업은 1번 컴퓨터, 2번 작업은 2번 컴퓨터, 3번 작업은 3번 컴퓨터, ...,

10번 작업은 10번 컴퓨터, 11번 작업은 1번 컴퓨터, 12번 작업은 2번 컴퓨터, ...

이런 식으로 번호를 다시 1번부터 차례로 돌려가며 작업을 맡긴다. 전체 작업의 개수는 항상 a^b개의 꼴로 주어진다. 마지막 작업을 맡게 되는 컴퓨터의 번호를 구하는 프로그램을 작성한다.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

각 테스트 케이스에 대해 마지막 작업을 맡게 되는 컴퓨터의 번호를 출력한다.