Server Time: Sun Sep 24, 2017 1:55 pm
Welcome ( logout
1070 - Algebraic Problem
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 00.

Output

For each test case, print the case number and (an+bn) modulo 264.

Sample Input

Output for Sample Input

2

10 16 2

7 12 3

Case 1: 68

Case 2: 91

 


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