Problem B
Yet another Number Sequence
Input: standard input
Output: standard output
Time Limit: 3 seconds

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

The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4].

Output

For each test case, print the last m digits of f(n). However, you should 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

89 4296 7711 946

---

Problem setter: Sadrul Habib Chowdhury

Special Thanks: Derek Kisman, Member of Elite Problem Setters’ Panel