It's a wonderful day, today is Salama's 20_th birthday.

Being joyful and triumphant, every year he gains the love of the people. He noticed that each year the number of friends t_i he makes increases by a factor r, while in his first year he made a friends. (a = r-1)

The number of friends he makes in the i_th year is a r^i-1.

It's commonly known that Salama loves math. Help him calculate S_n (the number of friends he will make in his first n years) modulo 1000003 (10⁶ + 3).

S_n = a + a r + a r² + a r³ + .... + a r^n-1

Note:
X modulo Y (X%Y) is the remainder of dividing X by Y. 

Input

Your program will be tested on one or more test cases. The first line of input will be a single integer T,
The number of test cases (1<=T<=20).Followed by T lines, each line consists of three integers a, r and n.
a = r-1
1 < r < 10
0 < n < 10⁶ (May he live long and happily!)

Output

For each test case, print “Case_#i:_X” where “X” is your answer modulo 1000003(10⁶ +3), “i” is the number of the test case (starting with 1) and “_” is a white space. Each output should be printed in a separate line.

Example

Input:
3
1 2 1
8 9 3
2 3 2

Output:
Case #1: 1
Case #2: 728
Case #3: 8