#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
namespace Factor {
const int N = 2010000;
long long C, fac[10010], n, mut, a[1001000];
int T, cnt, i, l, prime[N], p[N], psize, _cnt;
long long _e[100], _pr[100];
vector<long long> d;
inline long long mul(long long a, long long b, long long p) {
  if (p <= 1000000000)
    return a * b % p;
  else if (p <= 1000000000000ll)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    long long d = (long long)floor(a * (long double)b / p + 0.5);
    long long ret = (a * b - d * p) % p;
    if (ret < 0) ret += p;
    return ret;
  }
}
void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++) p[i] = i;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i) prime[++tot] = i;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
void init(int ps) {
  psize = ps;
  prime_table();
}
long long powl(long long a, long long n, long long p) {
  long long ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
  }
  return ans;
}
bool witness(long long a, long long n) {
  int t = 0;
  long long u = n - 1;
  for (; ~u & 1; u >>= 1) t++;
  long long x = powl(a, u, n), _x = 0;
  for (; t; t--) {
    _x = mul(x, x, n);
    if (_x == 1 && x != 1 && x != n - 1) return 1;
    x = _x;
  }
  return _x != 1;
}
bool miller(long long n) {
  if (n < 2) return 0;
  if (n <= psize) return p[n] == n;
  if (~n & 1) return 0;
  for (int j = 0; j <= 7; j++)
    if (witness(rand() % (n - 1) + 1, n)) return 0;
  return 1;
}
long long gcd(long long a, long long b) {
  long long ret = 1;
  while (a != 0) {
    if ((~a & 1) && (~b & 1))
      ret <<= 1, a >>= 1, b >>= 1;
    else if (~a & 1)
      a >>= 1;
    else if (~b & 1)
      b >>= 1;
    else {
      if (a < b) swap(a, b);
      a -= b;
    }
  }
  return ret * b;
}
long long rho(long long n) {
  for (;;) {
    long long X = rand() % n, Y, Z, T = 1, *lY = a, *lX = lY;
    int tmp = 20;
    C = rand() % 10 + 3;
    X = mul(X, X, n) + C;
    *(lY++) = X;
    lX++;
    Y = mul(X, X, n) + C;
    *(lY++) = Y;
    for (; X != Y;) {
      long long t = X - Y + n;
      Z = mul(T, t, n);
      if (Z == 0) return gcd(T, n);
      tmp--;
      if (tmp == 0) {
        tmp = 20;
        Z = gcd(Z, n);
        if (Z != 1 && Z != n) return Z;
      }
      T = Z;
      Y = *(lY++) = mul(Y, Y, n) + C;
      Y = *(lY++) = mul(Y, Y, n) + C;
      X = *(lX++);
    }
  }
}
void _factor(long long n) {
  for (int i = 0; i < cnt; i++) {
    if (n % fac[i] == 0) n /= fac[i], fac[cnt++] = fac[i];
  }
  if (n <= psize) {
    for (; n != 1; n /= p[n]) fac[cnt++] = p[n];
    return;
  }
  if (miller(n))
    fac[cnt++] = n;
  else {
    long long x = rho(n);
    _factor(x);
    _factor(n / x);
  }
}
void dfs(long long x, int dep) {
  if (dep == _cnt)
    d.push_back(x);
  else {
    dfs(x, dep + 1);
    for (int i = 1; i <= _e[dep]; i++) dfs(x *= _pr[dep], dep + 1);
  }
}
void norm() {
  sort(fac, fac + cnt);
  _cnt = 0;
  for (int i = 0; i < cnt; i++)
    if (i == 0 || fac[i] != fac[i - 1])
      _pr[_cnt] = fac[i], _e[_cnt++] = 1;
    else
      _e[_cnt - 1]++;
}
vector<long long> getd() {
  d.clear();
  dfs(1, 0);
  return d;
}
vector<long long> factor(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  return getd();
}
vector<pair<long long, long long> > factorG(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  vector<pair<long long, long long> > d;
  for (int i = 0; i < _cnt; i++) d.push_back(make_pair(_pr[i], _e[i]));
  return d;
}
bool is_primitive(long long a, long long p) {
  assert(miller(p));
  vector<pair<long long, long long> > D = factorG(p - 1);
  for (int i = 0; i < ((int)(D).size()); i++)
    if (powl(a, (p - 1) / D[i].first, p) == 1) return 0;
  return 1;
}
}  // namespace Factor
int pre[110][110], _;
long long n[10], m[10], s[10], ans;
int ppr[110], ff[110], ee[110], cntt;
map<long long, int> mn, mm, ms;
vector<long long> d;
void gao(long long *a, map<long long, int> &hs) {
  hs.clear();
  a[0] = a[1] * a[2] * a[3];
  for (int i = 1; i < 4; i++) {
    vector<pair<long long, long long> > d = Factor::factorG(a[i]);
    for (auto v : d) hs[v.first] += v.second;
  }
}
void dfs(long long x, int dep) {
  if (dep == cntt) {
    d.push_back(x);
  } else {
    dfs(x, dep + 1);
    for (int i = 1; i <= ee[dep]; i++) dfs(x *= ppr[dep], dep + 1);
  }
}
void dfs2(long long x, int dep, int sign) {
  if (sign == 0) return;
  if (dep == cntt) {
    ans += sign * (m[0] / x);
  } else {
    dfs2(x, dep + 1, sign * pre[0][ff[dep]]);
    for (int i = 1; i <= ee[dep]; i++)
      dfs2(x *= ppr[dep], dep + 1, sign * pre[i][ff[dep]]);
  }
}
void gen(map<long long, int> hs) {
  d.clear();
  cntt = 0;
  for (auto p : hs) ppr[cntt] = p.first, ee[cntt] = p.second, cntt++;
  dfs(1, 0);
}
int main() {
  for (int i = 0; i < 66; i++)
    for (int j = 0; j < 66; j++)
      for (int k = 0; k < i + 1; k++) {
        if (i - k > j) continue;
        if (k == 1)
          pre[i][j]--;
        else if (k == 0)
          pre[i][j]++;
      }
  Factor::init(2000000);
  for (scanf("%d", &_); _; _--) {
    for (int i = 1; i < 4; i++) scanf("%lld", n + i);
    gao(n, mn);
    for (int i = 1; i < 4; i++) scanf("%lld", m + i);
    gao(m, mm);
    for (int i = 1; i < 4; i++) scanf("%lld", s + i);
    s[1] *= 2;
    gao(s, ms);
    gen(ms);
    ans = 0;
    for (auto v : d)
      if (v <= n[0]) ans++;
    cntt = 0;
    for (auto p : mn) {
      ppr[cntt] = p.first;
      ff[cntt] = ms[p.first];
      ee[cntt] = p.second;
      cntt++;
    }
    dfs2(1, 0, 1);
    printf("%lld\n", ans);
  }
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Mister B has a house in the middle of a giant plain field, which attracted aliens life. For convenience, aliens specified the Cartesian coordinate system on the field in such a way that Mister B's house has coordinates (0, 0). After that they sent three beacons to the field, but something went wrong. One beacon was completely destroyed, while the other two landed in positions with coordinates (m, 0) and (0, n), respectively, but shut down.

Mister B was interested in this devices, so he decided to take them home. He came to the first beacon, placed at (m, 0), lifted it up and carried the beacon home choosing the shortest path. After that he came to the other beacon, placed at (0, n), and also carried it home choosing the shortest path. When first beacon was lifted up, the navigation system of the beacons was activated.

Partially destroyed navigation system started to work in following way.

At time moments when both survived beacons are at points with integer coordinates the system tries to find a location for the third beacon. It succeeds if and only if there is a point with integer coordinates such that the area of the triangle formed by the two survived beacons and this point is equal to s. In this case the system sends a packet of information with beacon positions to aliens, otherwise it doesn't.

Compute how many packets of information system sent while Mister B was moving the beacons.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. The next 3·t lines describe t test cases. 

Every test case is described in three lines as follows. Note that each parameter is given as a product of three factors.

The first line of a test case contains three space-separated integers: n1, n2, n3 (1 ≤ ni ≤ 106) such that n = n1·n2·n3.

The second line contains three space-separated integers: m1, m2, m3 (1 ≤ mi ≤ 106) such that m = m1·m2·m3.

The third line contains three space-separated integers: s1, s2, s3 (1 ≤ si ≤ 106) such that s = s1·s2·s3.

Note that for hacks only tests with t = 1 allowed.

Output

Print t integers one per line — the answers for each test.

Example

Input

3
2 1 1
2 1 1
1 1 3
1 5 1
2 2 1
1 1 2
10 6 18
2 103 2
13 1 13


Output

4
7
171

Note

First test case contains the following beacon positions: (2, 0) and (0, 2), s = 3. The following packets could be sent: ((2, 0), (0, 2), ( - 1, 0)), ((1, 0), (0, 2), (4, 0)), ((0, 0), (0, 2), (3, 1)), ((0, 0), (0, 1), ( - 6, 0)), where (b1, b2, p) has next description: b1 — first beacon position, b2 — second beacon position, p — some generated point.

Second test case contains the following beacon initial positions: (4, 0) and (0, 5), s = 2. The following packets could be sent: ((4, 0), (0, 5), (0, 4)), ((3, 0), (0, 5), (2, 3)), ((2, 0), (0, 5), (2, 2)), ((1, 0), (0, 5), (1, 4)), ((0, 0), (0, 4), (0, - 1)), ((0, 0), (0, 2), (2, 0)), ((0, 0), (0, 1), (4, 0)).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
namespace Factor {
const int N = 2010000;
long long C, fac[10010], n, mut, a[1001000];
int T, cnt, i, l, prime[N], p[N], psize, _cnt;
long long _e[100], _pr[100];
vector<long long> d;
inline long long mul(long long a, long long b, long long p) {
  if (p <= 1000000000)
    return a * b % p;
  else if (p <= 1000000000000ll)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    long long d = (long long)floor(a * (long double)b / p + 0.5);
    long long ret = (a * b - d * p) % p;
    if (ret < 0) ret += p;
    return ret;
  }
}
void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++) p[i] = i;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i) prime[++tot] = i;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
void init(int ps) {
  psize = ps;
  prime_table();
}
long long powl(long long a, long long n, long long p) {
  long long ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
  }
  return ans;
}
bool witness(long long a, long long n) {
  int t = 0;
  long long u = n - 1;
  for (; ~u & 1; u >>= 1) t++;
  long long x = powl(a, u, n), _x = 0;
  for (; t; t--) {
    _x = mul(x, x, n);
    if (_x == 1 && x != 1 && x != n - 1) return 1;
    x = _x;
  }
  return _x != 1;
}
bool miller(long long n) {
  if (n < 2) return 0;
  if (n <= psize) return p[n] == n;
  if (~n & 1) return 0;
  for (int j = 0; j <= 7; j++)
    if (witness(rand() % (n - 1) + 1, n)) return 0;
  return 1;
}
long long gcd(long long a, long long b) {
  long long ret = 1;
  while (a != 0) {
    if ((~a & 1) && (~b & 1))
      ret <<= 1, a >>= 1, b >>= 1;
    else if (~a & 1)
      a >>= 1;
    else if (~b & 1)
      b >>= 1;
    else {
      if (a < b) swap(a, b);
      a -= b;
    }
  }
  return ret * b;
}
long long rho(long long n) {
  for (;;) {
    long long X = rand() % n, Y, Z, T = 1, *lY = a, *lX = lY;
    int tmp = 20;
    C = rand() % 10 + 3;
    X = mul(X, X, n) + C;
    *(lY++) = X;
    lX++;
    Y = mul(X, X, n) + C;
    *(lY++) = Y;
    for (; X != Y;) {
      long long t = X - Y + n;
      Z = mul(T, t, n);
      if (Z == 0) return gcd(T, n);
      tmp--;
      if (tmp == 0) {
        tmp = 20;
        Z = gcd(Z, n);
        if (Z != 1 && Z != n) return Z;
      }
      T = Z;
      Y = *(lY++) = mul(Y, Y, n) + C;
      Y = *(lY++) = mul(Y, Y, n) + C;
      X = *(lX++);
    }
  }
}
void _factor(long long n) {
  for (int i = 0; i < cnt; i++) {
    if (n % fac[i] == 0) n /= fac[i], fac[cnt++] = fac[i];
  }
  if (n <= psize) {
    for (; n != 1; n /= p[n]) fac[cnt++] = p[n];
    return;
  }
  if (miller(n))
    fac[cnt++] = n;
  else {
    long long x = rho(n);
    _factor(x);
    _factor(n / x);
  }
}
void dfs(long long x, int dep) {
  if (dep == _cnt)
    d.push_back(x);
  else {
    dfs(x, dep + 1);
    for (int i = 1; i <= _e[dep]; i++) dfs(x *= _pr[dep], dep + 1);
  }
}
void norm() {
  sort(fac, fac + cnt);
  _cnt = 0;
  for (int i = 0; i < cnt; i++)
    if (i == 0 || fac[i] != fac[i - 1])
      _pr[_cnt] = fac[i], _e[_cnt++] = 1;
    else
      _e[_cnt - 1]++;
}
vector<long long> getd() {
  d.clear();
  dfs(1, 0);
  return d;
}
vector<long long> factor(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  return getd();
}
vector<pair<long long, long long> > factorG(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  vector<pair<long long, long long> > d;
  for (int i = 0; i < _cnt; i++) d.push_back(make_pair(_pr[i], _e[i]));
  return d;
}
bool is_primitive(long long a, long long p) {
  assert(miller(p));
  vector<pair<long long, long long> > D = factorG(p - 1);
  for (int i = 0; i < ((int)(D).size()); i++)
    if (powl(a, (p - 1) / D[i].first, p) == 1) return 0;
  return 1;
}
}  // namespace Factor
int pre[110][110], _;
long long n[10], m[10], s[10], ans;
int ppr[110], ff[110], ee[110], cntt;
map<long long, int> mn, mm, ms;
vector<long long> d;
void gao(long long *a, map<long long, int> &hs) {
  hs.clear();
  a[0] = a[1] * a[2] * a[3];
  for (int i = 1; i < 4; i++) {
    vector<pair<long long, long long> > d = Factor::factorG(a[i]);
    for (auto v : d) hs[v.first] += v.second;
  }
}
void dfs(long long x, int dep) {
  if (dep == cntt) {
    d.push_back(x);
  } else {
    dfs(x, dep + 1);
    for (int i = 1; i <= ee[dep]; i++) dfs(x *= ppr[dep], dep + 1);
  }
}
void dfs2(long long x, int dep, int sign) {
  if (sign == 0) return;
  if (dep == cntt) {
    ans += sign * (m[0] / x);
  } else {
    dfs2(x, dep + 1, sign * pre[0][ff[dep]]);
    for (int i = 1; i <= ee[dep]; i++)
      dfs2(x *= ppr[dep], dep + 1, sign * pre[i][ff[dep]]);
  }
}
void gen(map<long long, int> hs) {
  d.clear();
  cntt = 0;
  for (auto p : hs) ppr[cntt] = p.first, ee[cntt] = p.second, cntt++;
  dfs(1, 0);
}
int main() {
  for (int i = 0; i < 66; i++)
    for (int j = 0; j < 66; j++)
      for (int k = 0; k < i + 1; k++) {
        if (i - k > j) continue;
        if (k == 1)
          pre[i][j]--;
        else if (k == 0)
          pre[i][j]++;
      }
  Factor::init(2000000);
  for (scanf("%d", &_); _; _--) {
    for (int i = 1; i < 4; i++) scanf("%lld", n + i);
    gao(n, mn);
    for (int i = 1; i < 4; i++) scanf("%lld", m + i);
    gao(m, mm);
    for (int i = 1; i < 4; i++) scanf("%lld", s + i);
    s[1] *= 2;
    gao(s, ms);
    gen(ms);
    ans = 0;
    for (auto v : d)
      if (v <= n[0]) ans++;
    cntt = 0;
    for (auto p : mn) {
      ppr[cntt] = p.first;
      ff[cntt] = ms[p.first];
      ee[cntt] = p.second;
      cntt++;
    }
    dfs2(1, 0, 1);
    printf("%lld\n", ans);
  }
}

```