Server Time: Mon Sep 21, 2020 12:35 am
Welcome ( logout
G - Number Sequence
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Let's define another number sequence, given by the following function:

f(0) = a

f(1) = b

f(n) = f(n-1) + f(n-2), n > 1

When a = 0 and b = 1, this sequence gives the Fibonacci sequence. Changing the values of a and b, you can get many different sequences. Given the values of a, b, you have to find the last m 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 Input

Output for Sample Input

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

 


Special Thanks: Jane Alam Jan (Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan