Metro Turnstiles
Time limit2sMemory limit256 MB
Two card counters a and b decrease daily, displayed as min(value, 99); find the first day one display equals k times the other, or -1.
- Level
Medium7 of 10
- Topics
- Math, Implementation, Brute force, Simulation
- Solved
- No attempts yet
Problem
Vasya and Petya ride the metro every day, so they decided to buy travel cards instead of buying a token each time. Each card can be used for a certain number of days, after which it becomes inactive.
Every time you pass through a turnstile, it displays how many days the card can still be used (including the current day). Unfortunately, the display that shows this number can only show one-digit and two-digit numbers. If the number to display has at least three digits, the display shows the number 99. For example, if a card has 5 days left, the turnstile shows 5; if 12 days are left, it shows 12; and if 123 days are left, the turnstile shows 99. If 0 days remain on a card, it becomes inactive and you can no longer pass through the turnstile with it.
Right now Vasya's card has a days left and Petya's has b. They ride the metro every day and look at the numbers shown on the turnstile every day. They became curious: after how many days will the number on one of their turnstiles be exactly k times the number on the other's for the first time? Help the friends find the answer to this question.
Input
The first line of the input contains a single number t (1 ≤ t ≤ 100000), the number of tests. The next t lines each contain one test. Each test is given by three integers: a, b, k (1 ≤ a, b ≤ 2·10^9, 1 ≤ k ≤ 100), the number of days remaining on Vasya's and Petya's cards and the required ratio.
Output
For each test, output a single number: after how many days the number shown on one friend's turnstile will be k times the number shown on the other's. If this does not happen before the day one of the friends' cards becomes inactive, output "-1".