Problem: A frog is currently at the point 0 on a coordinate axis Ox. It jumps by the following algorithm: the first jump is a units to the right, the second jump is b units to the left, the third jump is a units to the right, the fourth jump is b units to the left, and so on.

Formally: 

  * if the frog has jumped an even number of times (before the current jump), it jumps from its current position x to position x+a; 
  * otherwise it jumps from its current position x to position x-b. 



Your task is to calculate the position of the frog after k jumps.

But... One more thing. You are watching t different frogs so you have to answer t independent queries.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 1000) — the number of queries.

Each of the next t lines contain queries (one query per line).

The query is described as three space-separated integers a, b, k (1 ≤ a, b, k ≤ 10^9) — the lengths of two types of jumps and the number of jumps, respectively.

Output

Print t integers. The i-th integer should be the answer for the i-th query.

Example

Input


6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999


Output


8
198
-17
2999999997
0
1

Note

In the first query frog jumps 5 to the right, 2 to the left and 5 to the right so the answer is 5 - 2 + 5 = 8.

In the second query frog jumps 100 to the right, 1 to the left, 100 to the right and 1 to the left so the answer is 100 - 1 + 100 - 1 = 198.

In the third query the answer is 1 - 10 + 1 - 10 + 1 = -17.

In the fourth query the answer is 10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997.

In the fifth query all frog's jumps are neutralized by each other so the answer is 0.

The sixth query is the same as the fifth but without the last jump so the answer is 1.

Solution (in JAVA):

Solution:
//Written by Shagoto
import java.util.*;
import java.io.*;
public class Main
{
// -------- Generating Prime Numbers Using Bit-wise sieve --------
//  static HashSet<Integer> primes = new HashSet<Integer>();
//  static BitSet bs = new BitSet(10000001);
//  static void sieve()
//  {
//    primes.add(2);
//    for(int i = 4; i<=10000000; i+=2)
//    {
//      bs.set(i,true);
//    }
//    
//    for(int i = 3; i<=10000000; i+=2)
//    {
//      if(!bs.get(i))
//      {
//        primes.add(i);
//        for(int j = 3; i*j<=10000000; j+=2)
//        {
//          bs.set(i*j,true);
//        }
//      }
//    }
//  }
  
// -------- Lowerbound --------
//  static int lowerBound(long [] arr, long x)
//  {
//    int low = 0;
//    int high = arr.length - 1;
//    int mid = 0;
//    while(low < high)
//    {
//      mid = (start + end) / 2;
//      int mid = (low + high) / 2;
//      
//      if(arr[mid] == x)
//      {
//        return mid;
//      }
//      else if(arr[mid] > x)
//      {
//        high = mid - 1;
//      }
//      else
//      {
//        low = mid + 1;
//      }
//    }
//    
//    if(arr[mid] > x)
//    {
//      if(mid - 1 >= 0 && arr[mid - 1] < x)
//      {
//        return mid - 1;
//      }
//      return -1;
//    }
//    return mid;
//  }
  
// -------- Prefix Sum --------
// If zero indexed, add 1  
// pref.add(0)  
// pref.get(r) - pref.get(l - 1)
// xor(l, r) = pref[r]^pref[l - 1]
  
// -------- Ceil --------
//  static int ceil(int n, int x)
//  {
//    if(n / x * x != n)
//    {
//      return n / x + 1;
//    }
//    return n / x;
//  }
  
// -------- Phi Function --------
//  static int phi(int n) 
//  { 
//    int ret = n;  
//    for(int i = 2; i*i <= n; i++) 
//    { 
//      if(n % i == 0)  
//      { 
//        while(n % i == 0) 
//        {
//          n /= i; 
//        }
//        ret -= ret / i; 
//      } 
//    } 
//    
//    if(n > 1) 
//    {
//      ret -= ret / n; 
//    }
//    return ret; 
//  }
  
// -------- GCD of Two Numbers --------  
//  static int gcd(int a, int b)
//  {
//    if(b == 0)
//    {
//      return a;
//    }
//    return gcd(b, a % b);  
//  }
  
// -------- LCM of two Numbers --------
//  static int lcm(int a, int b)
//  {
//    return (a * b) / gcd(a, b);
//  }
  
//  -------- Binary Search --------
//  static int binarySearch(int [] arr, int x)
//  {
//    int low = 0;
//    int high = arr.length - 1;
//    
//    while(low <= high)
//    {
//      int mid = (low + high) / 2;
//      
//      if(arr[mid] == x)
//      {
//        return mid;
//      }
//      else if(arr[mid] > x)
//      {
//        high = mid - 1;
//      }
//      else
//      {
//        low = mid + 1;
//      }
//    }
//    return -1;
//  }
  
  public static void main(String[]args) throws IOException
  {
/*    
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader read = new BufferedReader(isr);
*/    
    Scanner read = new Scanner(System.in);
    
    int t = read.nextInt();
    for(int x = 1; x<=t; x++)
    {
      long a = read.nextLong();
      long b = read.nextLong();
      long k = read.nextLong();
      System.out.println((k - (k / 2)) * a -(k / 2 * b));
    }
  }
}

// -------- Creating own Class --------
//class className
//{
//  int v1;
//  int v2;
//  public className(int x, int y)
//  {
//    v1 = x;
//    v2 = y;
//  }
// 
//  public String toString()
//  {
//    return v1+" "+v2;
//  }
//}

// -------- For Comparision or Sorting --------
// *Paste it in the main class*
//Collections.sort(arr, new Comparator<className>(){
//      public int compare(className a, className b)
//      {
//        if(a.v1 == b.v1)
//        {
//          return b.v2 - a.v2;
//        }
//        else
//        {
//          return a.v1 - b.v1;
//        }
//      }
//    });