#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (a > b) {
    a = a + b;
    b = a - b;
    a = a - b;
  }
  if (b % a == 0) return a;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long prime[1000], pcnt;
long long defac[1000][2], dcnt;
long long era[1000];
long long input[1000];
void defac_precompute(long long maxnum) {
  long long i, j;
  for (i = 2; i <= maxnum; i++) era[i] = i;
  pcnt = 0;
  for (i = 2; i <= maxnum; i++) {
    if (era[i] == 0) continue;
    prime[pcnt++] = i;
    j = i;
    while (j <= maxnum) {
      era[j] = 0;
      j += i;
    }
  }
}
long long prdfac(long long x) {
  long long i, bx = x, p1 = 1, p2 = 1, cnt;
  dcnt = 0;
  for (i = 0; i < pcnt; i++) {
    if (bx % prime[i] == 0) {
      defac[dcnt][0] = prime[i];
      defac[dcnt][1] = 0;
      while (bx % prime[i] == 0) {
        bx /= prime[i];
        defac[dcnt][1]++;
      }
      dcnt++;
    }
    if (bx == 1) break;
  }
  if (bx > 1) {
    defac[dcnt][0] = bx;
    defac[dcnt][1] = 1;
    dcnt++;
  }
  return 1;
}
tuple<long long, long long, long long> extended_euclidean(long long a,
                                                          long long b) {
  if (b == 0) return make_tuple(a, 1, 0);
  long long g, x, y;
  tie(g, x, y) = extended_euclidean(b, a % b);
  return make_tuple(g, y, x - (a / b) * y);
}
long long fac[1000];
long long invfac[1000];
void comb_preprocess(long long maxval) {
  invfac[0] = invfac[1] = fac[0] = fac[1] = 1;
  for (long long i = 2; i <= maxval; i++)
    fac[i] = (long long)fac[i - 1] * i % 1000000007;
  for (long long i = 2; i <= maxval; i++)
    invfac[i] = (long long)(1000000007 - (1000000007 / i)) *
                invfac[1000000007 % i] % 1000000007;
  for (long long i = 2; i <= maxval; i++)
    invfac[i] = (long long)invfac[i - 1] *
                ((invfac[i] + 1000000007) % 1000000007) % 1000000007;
}
long long Comb(long long n, long long r) {
  return (long long)fac[n] * invfac[r] % 1000000007 * invfac[n - r] %
         1000000007;
}
vector<long long> getPi(string p) {
  long long m = (long long)p.size(), j = 0;
  vector<long long> pi(m, 0);
  for (long long i = 1; i < m; i++) {
    while (j > 0 && p[i] != p[j]) j = pi[j - 1];
    if (p[i] == p[j]) pi[i] = ++j;
  }
  return pi;
}
string common(const string& word, const string& rev) {
  vector<long long> pi = getPi(rev);
  long long m = word.size();
  long long begin = 0, matched = 0;
  while (begin + matched < m) {
    if (word[begin + matched] == rev[matched]) {
      matched++;
      if (begin + matched == m) {
        break;
      }
    } else {
      if (matched == 0) {
        begin++;
      } else {
        begin += matched - pi[matched - 1];
        matched = pi[matched - 1];
      }
    }
  }
  return word.substr(begin, m - begin);
}
bool isPrime(long long n) {
  long long cl = (long long)sqrt(n);
  for (long long x = 2; x <= cl; x++)
    if (n % x == 0) return false;
  return true;
}
void prvec(vector<long long>& vv, string sss) {
  cout << sss;
  printf(" vec_is :: ");
  for (long long i = 0; i < (vv.size()); i++) printf("%d ", vv[i]);
  printf("\n");
}
void prlst(list<long long>& vv, string sss) {
  list<long long>::iterator it;
  cout << sss;
  printf(" vec_is :: ");
  for (it = vv.begin(); it != vv.end(); it++) printf("%d ", *it);
  printf("\n");
}
long long ten[10];
long long XC2(long long x) {
  if (x <= 1)
    return 0;
  else
    return x * (x - 1) / 2;
}
void solve(long long tc) {
  long long m, d, w, l, md, q, r;
  cin >> m >> d >> w;
  if (d == 1) {
    cout << 0 << endl;
    return;
  }
  l = (((m) < (d)) ? (m) : (d));
  md = w / gcd(d - 1, w);
  q = l / md;
  r = l % md;
  cout << (md - r) * XC2(q) + r * XC2(q + 1) << endl;
}
signed main() {
  long long T = 1, tc;
  cin >> T;
  for (tc = 1; tc <= T; tc++) solve(tc);
}

### Prompt

In Cpp, your task is to solve the following problem:

Berland year consists of m months with d days each. Months are numbered from 1 to m. Berland week consists of w days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than w days.

A pair (x, y) such that x < y is ambiguous if day x of month y is the same day of the week as day y of month x.

Count the number of ambiguous pairs.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Each of the next t lines contains three integers m, d and w (1 ≤ m, d, w ≤ 10^9) — the number of months in a year, the number of days in a month and the number of days in a week.

Output

Print t integers — for each testcase output the number of pairs (x, y) such that x < y and day x of month y is the same day of the week as day y of month x.

Example

Input


5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324


Output


6
9
5
0
116461800

Note

Here are the pairs for the first test case: 

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (a > b) {
    a = a + b;
    b = a - b;
    a = a - b;
  }
  if (b % a == 0) return a;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long prime[1000], pcnt;
long long defac[1000][2], dcnt;
long long era[1000];
long long input[1000];
void defac_precompute(long long maxnum) {
  long long i, j;
  for (i = 2; i <= maxnum; i++) era[i] = i;
  pcnt = 0;
  for (i = 2; i <= maxnum; i++) {
    if (era[i] == 0) continue;
    prime[pcnt++] = i;
    j = i;
    while (j <= maxnum) {
      era[j] = 0;
      j += i;
    }
  }
}
long long prdfac(long long x) {
  long long i, bx = x, p1 = 1, p2 = 1, cnt;
  dcnt = 0;
  for (i = 0; i < pcnt; i++) {
    if (bx % prime[i] == 0) {
      defac[dcnt][0] = prime[i];
      defac[dcnt][1] = 0;
      while (bx % prime[i] == 0) {
        bx /= prime[i];
        defac[dcnt][1]++;
      }
      dcnt++;
    }
    if (bx == 1) break;
  }
  if (bx > 1) {
    defac[dcnt][0] = bx;
    defac[dcnt][1] = 1;
    dcnt++;
  }
  return 1;
}
tuple<long long, long long, long long> extended_euclidean(long long a,
                                                          long long b) {
  if (b == 0) return make_tuple(a, 1, 0);
  long long g, x, y;
  tie(g, x, y) = extended_euclidean(b, a % b);
  return make_tuple(g, y, x - (a / b) * y);
}
long long fac[1000];
long long invfac[1000];
void comb_preprocess(long long maxval) {
  invfac[0] = invfac[1] = fac[0] = fac[1] = 1;
  for (long long i = 2; i <= maxval; i++)
    fac[i] = (long long)fac[i - 1] * i % 1000000007;
  for (long long i = 2; i <= maxval; i++)
    invfac[i] = (long long)(1000000007 - (1000000007 / i)) *
                invfac[1000000007 % i] % 1000000007;
  for (long long i = 2; i <= maxval; i++)
    invfac[i] = (long long)invfac[i - 1] *
                ((invfac[i] + 1000000007) % 1000000007) % 1000000007;
}
long long Comb(long long n, long long r) {
  return (long long)fac[n] * invfac[r] % 1000000007 * invfac[n - r] %
         1000000007;
}
vector<long long> getPi(string p) {
  long long m = (long long)p.size(), j = 0;
  vector<long long> pi(m, 0);
  for (long long i = 1; i < m; i++) {
    while (j > 0 && p[i] != p[j]) j = pi[j - 1];
    if (p[i] == p[j]) pi[i] = ++j;
  }
  return pi;
}
string common(const string& word, const string& rev) {
  vector<long long> pi = getPi(rev);
  long long m = word.size();
  long long begin = 0, matched = 0;
  while (begin + matched < m) {
    if (word[begin + matched] == rev[matched]) {
      matched++;
      if (begin + matched == m) {
        break;
      }
    } else {
      if (matched == 0) {
        begin++;
      } else {
        begin += matched - pi[matched - 1];
        matched = pi[matched - 1];
      }
    }
  }
  return word.substr(begin, m - begin);
}
bool isPrime(long long n) {
  long long cl = (long long)sqrt(n);
  for (long long x = 2; x <= cl; x++)
    if (n % x == 0) return false;
  return true;
}
void prvec(vector<long long>& vv, string sss) {
  cout << sss;
  printf(" vec_is :: ");
  for (long long i = 0; i < (vv.size()); i++) printf("%d ", vv[i]);
  printf("\n");
}
void prlst(list<long long>& vv, string sss) {
  list<long long>::iterator it;
  cout << sss;
  printf(" vec_is :: ");
  for (it = vv.begin(); it != vv.end(); it++) printf("%d ", *it);
  printf("\n");
}
long long ten[10];
long long XC2(long long x) {
  if (x <= 1)
    return 0;
  else
    return x * (x - 1) / 2;
}
void solve(long long tc) {
  long long m, d, w, l, md, q, r;
  cin >> m >> d >> w;
  if (d == 1) {
    cout << 0 << endl;
    return;
  }
  l = (((m) < (d)) ? (m) : (d));
  md = w / gcd(d - 1, w);
  q = l / md;
  r = l % md;
  cout << (md - r) * XC2(q) + r * XC2(q + 1) << endl;
}
signed main() {
  long long T = 1, tc;
  cin >> T;
  for (tc = 1; tc <= T; tc++) solve(tc);
}

```