긴 나눗셈

옛날(대략 1965년경)의 기계식 계산기는 자리 이동과 반복 뺄셈으로 나눗셈을 수행했다. 예를 들어 987654321을 3456789로 나눌 때, 먼저 두 수를 가장 왼쪽 자리에 맞추어 정렬한 뒤(아래 (1) 참고), 결과가 음수가 되지 않는 범위에서 나누는 수를 나누어지는 수로부터 최대한 여러 번 뺀다. 성공한 뺄셈의 횟수(이 예에서는 2번)가 몫의 첫 번째 자리 숫자가 된다. 그다음 나누는 수를 오른쪽으로 한 자리 이동시켜(아래 (2) 참고) 남은 값에서 다시 여러 번 빼면 몫의 다음 자리 숫자를 얻는다. 남은 값이 나누는 수보다 작아질 때까지 이 과정을 반복한다.

이 나눗셈 방법을 구현하는 프로그램을 작성하시오.

첫 번째 줄에는 뒤따르는 테스트 케이스의 개수를 나타내는 양의 정수 $n$ ($n \le 20$)이 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 첫 번째 줄은 나누어지는 수(피제수), 두 번째 줄은 나누는 수(제수)이다. 각 줄에는 최대 80자리의 양의 정수가 주어진다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 번째 줄에는 몫을, 두 번째 줄에는 나머지를 출력한다. 서로 다른 테스트 케이스의 출력은 빈 줄 하나로 구분한다. 불필요한 앞자리 0은 출력하지 않는다.

피제수가 $n$자리, 제수가 $m$자리일 때, 프로그램이 수행하는 한 자리 뺄셈의 최대 횟수를 $n$과 $m$에 대한 식으로 근사하여 나타내어 보시오.