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

$$ f(n) = \begin{cases} a, & \text{if $n$ = 0} \\ b, & \text{if $n$ = 1} \\ f(n - 1) + f(n - 2), & \text{if $n$ > 1} \end{cases} $$

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 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, 10⁹] and value of m ranges in [1, 4].

For each case, print the case number and the last m digits of f(n). However, do NOT print any leading zero.