BUET Inter-University Programming Contest
Problem
H – Happy 10/9 Day
Problem
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 
denoting the number of test cases. Then in
each of the following T lines, there will be 4 integers n, b,
d and M 
. 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 |
Output for Sample Input |
|
1 3 10 2 10 |
Case 1: 2 |
|
|
|
Problemsetter:
|
Md. Mahbubul Hasan |
Special Thanks:
|
Anindya Das
|