지하철 개찰구
시간 제한2초메모리 제한256 MB
두 카드의 잔여 일수 a와 b가 매일 줄어들고 표시값은 min(값, 99)일 때, 한 표시가 다른 표시의 k배가 되는 첫날을 구하거나 -1을 출력한다.
문제
Вася와 Петя는 매일 지하철을 타므로 매번 토큰을 사지 않으려고 교통카드를 사기로 했다. 각 카드는 정해진 일수 동안 사용할 수 있고, 그 뒤에는 비활성화된다.
개찰구를 통과할 때마다 카드를 며칠 더 사용할 수 있는지(당일 포함)가 표시된다. 그런데 이 일수를 보여 주는 전광판은 한 자리 수와 두 자리 수만 표시할 수 있다. 표시할 수에 자릿수가 세 자리 이상이면 전광판에는 99가 표시된다. 예를 들어 카드에 5일이 남았다면 개찰구에는 5가, 12일이 남았다면 12가, 123일이 남았다면 99가 표시된다. 카드에 남은 일수가 0이면 카드는 비활성화되어 더 이상 개찰구를 통과할 수 없다.
지금 Вася의 카드에는 a일이, Петя의 카드에는 b일이 남아 있다. 두 사람은 매일 지하철을 타고 매일 개찰구에 표시되는 수를 본다. 그러던 중 두 사람은 궁금해졌다. 두 사람 중 한 사람의 개찰구 수가 다른 사람의 개찰구 수보다 정확히 k배가 되는 날이 며칠 뒤에 처음 오는가? 친구들이 이 질문에 답을 찾도록 도와주자.
입력
첫 번째 줄에는 테스트의 수 t (1 ≤ t ≤ 100000)가 주어진다. 다음 t개 줄에는 각각 하나의 테스트가 주어진다. 각 테스트는 세 정수 a, b, k (1 ≤ a, b ≤ 2·10^9, 1 ≤ k ≤ 100)로 주어진다. a와 b는 Вася와 Петя의 카드에 남은 일수이고, k는 요구하는 비율이다.
출력
각 테스트마다 한 수를 출력한다. 두 친구 중 한 사람의 개찰구 수가 다른 사람보다 k배가 되는 날이 며칠 뒤인지 출력한다. 두 사람 중 한 사람의 카드가 비활성화되는 날까지 그런 일이 일어나지 않으면 «-1»을 출력한다.