The a-b-c Calculator Filename: calc.java Standard Input, Standard Output You bought a calculator at a garage sale for only 25 cents, thinking you got a steal. Unfortunately, the calculator has very limited functionality and a rather strange screen. The initial display always starts with 0 on it and there are three buttons you can press which perform the following operations on the current number on the screen: (1) Add a (2) Multiply by b (3) Integer Division by c where a, b, and c are given for each different calculator. The screen displays exactly 6 digits, and when you attempt a calculation with a result one million or greater, you realize that the display shows the last six digits of the actual correct response and uses this value instead for the next calculation. (For example, if the display showed 345678 and b = 3, if we press the button to multiply by 3, the resulting value will be 037034, the last six digits of the actual result. If we then pressed the integer divide button by c = 4, the new result would be 9258. Note that this is different than 1037034/4.) Given the constants a, b, and c, described above, and a target integer, t, determine the minimum number of button presses needed to obtain t on the calculator display. Input The first line will contain a single positive integer, n, (n ≤ 100), specifying the number of input cases. Each input case will be on a single line having four space-separated positive integers, a, b, c and t, representing the additive constant, multiplicative constant, division constant and target value for the test case (1 ≤ a, b, c ≤ 1000, 1 ≤ t ≤ 999999). Output For each test case, on a line by itself, output the minimum number of button presses necessary to obtain the target for the case. If it’s impossible to obtain the target, print out a -1 on a line by itself instead. Samples Input Output 3 1 3 2 197 10 30 1 5 1 7 2 123456 11 -1 17
