2011 is a very special year. There appeared some amazing dates in this year which would appear every 100 years. 1-1-11, 1-11-11, 11-1-11, 11-11-11 are some of many amazing dates. Oh, by the way, I hope you already found out why the problem name says 10/9. If you convert it to decimal then you will find series of 1 appears. However same logic applies for 1/9 or 100/9 also. This problem is related with same digit appearance. In short the problem asks you to find X%M where X is an n-digit number consisting only of digit d. But we are a bit visionary. We want to generalize this problem a bit. Who knows one day we will not use 10 base number system anymore, may be 2 base, or 16 base or any other number! So you have to calculate the value considering the number in base b (d < b). For example, for b = 10, n = 3, d = 2 our X = 222. So if our M is say 10, then X%M = 2 which is the answer. Input First line of the input contains a single positive integer T (1 ≤ T ≤ 1, 000) denoting the number of test cases. Then in each of the following T lines, there will be 4 integers n, b, d and M (2 ≤ b le100 and 1 ≤ n, M ≤ 1012). All these numbers are given in base 10. Output For each of the cases output the case number followed by the desired answer. For clarity please follow the sample input output. Remember that this output should always be in base 10, irrespective of the input. Sample Input 1 3 10 2 10 Sample Output Case 1: 2