Let's define another number sequence, given by the following function:
f(n)={a,if n = 0b,if n = 1f(n−1)+f(n−2),if n > 1
When a = 0 and b = 1, this sequence gives the Fibonacci sequence. Changing the values of a and b, you will be able to get many different sequences.
Given the values of a, b, you have to find the least m significant digits of f(n).
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each test case consists of a single line containing four integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 109] and value of m ranges in [1, 4].
Output
For each case, print the case number and the last m digits of f(n). However, do NOT print any leading zero.
Sample
Sample Input | Sample Output |
---|---|
4 0 1 11 3 0 1 42 4 0 1 22 4 0 1 21 4 | Case 1: 89 Case 2: 4296 Case 3: 7711 Case 4: 946 |