오사마 교수의 예산
면접 대비시간 제한1초메모리 제한256 MB
최대 백만 자릿수의 자금 N을 팀 수 X로 나눈 나머지를 각 테스트 케이스마다 구합니다.
문제
오사마 이스마일 교수는 ACPC 지역 대회를 총괄한다. 어느 해에 그는 예산을 이렇게 짜기로 했다. 모든 팀에 같은 금액 를 나눠 주고, 는 가능한 한 크게 잡는다. 즉 한 팀 몫도 채우지 못할 만큼만 남을 때까지 기금을 똑같이 쪼개어 배분한다. 그렇게 배분하고 남은 돈은 대회 운영에 필요한 다른 곳에 쓴다.
그해 모금이 잘돼서 기금 은 자릿수가 매우 많을 수 있다. 기금 과 팀 수 가 주어질 때, 다른 곳에 쓸 돈이 얼마인지 구하라.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다 ().
이어지는 개의 줄에 각각 두 정수 과 가 공백으로 구분되어 주어진다. 은 모인 기금으로, 앞에 이 붙지 않는 양의 정수이며 자릿수는 최대 100만이다. 는 팀 수이다 ().
출력
각 테스트 케이스마다 Case n: R 형식으로 한 줄씩 출력한다. 은 부터 시작하는 테스트 케이스 번호이고, 은 대회 운영의 다른 곳에 쓸 돈이다.