22066번 - Турникеты в метро 다국어

Вася и Петя каждый день ездят на метро, поэтому они решили купить себе проездные карты, чтобы каждый раз не покупать жетон. Каждая карта может использоваться в течение определенного количества дней, после чего она становится неактивной.

При каждом проходе через турникет высвечивается, сколько еще дней карта может быть использована (включая текущий день). Но, к сожалению, табло, на котором это количество дней отображается, может показывать только однозначные и двузначные числа. Если же в отображаемом числе хотя бы три цифры, на табло покажется число 99. Например, если на карте осталось 5 дней, то на турникете покажется число 5, если 12 дней, то число 12, а если 123 дня, то на турникете покажется число 99. Если на карте остается 0 дней, она становится неактивной и по ней больше нельзя проходить через турникет.

Сейчас у Васи на карте осталось a дней, а у Пети — b. Они каждый день ездят на метро и каждый день смотрят на числа, которые отображаются на турникете. И им стало интересно: через сколько дней в первый раз число на турникете у одного из них будет ровно в k раз больше, чем число на турникете у другого. Помогите друзьям выяснить ответ на этот вопрос.

Первая строка входных данных содержит одно число t (1 ≤ t ≤ 100000) — количество тестов. Следующие t строк содержат по тесту каждая. Каждый тест задается тремя целыми числами: a, b, k (1 ≤ a, b ≤ 2·10⁹, 1 ≤ k ≤ 100) — количество оставшихся дней на карточках у Васи и Пети и требуемое отношение.

Для каждого набора данных выведите единственное число: через сколько дней у одного из друзей на турникете будет показано в k раз больше поездок, чем у другого. Если такого не произойдет до того дня, когда у одного из друзей карта станет неактивной, выведите «-1».