#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (int i = 0; i < (((int)(v).size())); ++i) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  return os << "(" << p.first << " " << p.second << ")";
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;
template <int64_t mod>
class modint {
  int64_t x;

 public:
  modint(int64_t x = 0) : x(x < 0 ? ((x % mod) + mod) % mod : x % mod) {}
  const modint operator-() const { return x == 0 ? 0 : mod - x; }
  modint& operator+=(const modint& rhs) {
    if ((x += rhs.x) >= mod) x -= mod;
    return *this;
  }
  modint& operator-=(const modint& rhs) { return *this += -rhs; }
  modint& operator*=(const modint& rhs) {
    (x *= rhs.x) %= mod;
    return *this;
  }
  modint& operator/=(const modint& rhs) { return *this *= rhs.pow(mod - 2); }
  friend const modint operator+(modint lhs, const modint& rhs) {
    return lhs += rhs;
  }
  friend const modint operator-(modint lhs, const modint& rhs) {
    return lhs -= rhs;
  }
  friend const modint operator*(modint lhs, const modint& rhs) {
    return lhs *= rhs;
  }
  friend const modint operator/(modint lhs, const modint& rhs) {
    return lhs /= rhs;
  }
  const modint pow(int64_t n) const {
    modint ret = 1, tmp = *this;
    while (n) {
      if (n & 1) ret *= tmp;
      tmp *= tmp;
      n >>= 1;
    }
    return ret;
  }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.x == rhs.x;
  }
  friend bool operator!=(const modint& lhs, const modint& rhs) {
    return lhs.x != rhs.x;
  }
  friend ostream& operator<<(ostream& os, const modint& a) { return os << a.x; }
  friend istream& operator>>(istream& is, modint& a) {
    int64_t tmp;
    is >> tmp;
    a = tmp;
    return is;
  }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int T;
  cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    cout << (n % m == 0 ? "YES" : "NO") << endl;
  }
  return 0;
}

### Prompt

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

You are given two integers n and m (m < n). Consider a convex regular polygon of n vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).

<image> Examples of convex regular polygons 

Your task is to say if it is possible to build another convex regular polygon with m vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The next t lines describe test cases. Each test case is given as two space-separated integers n and m (3 ≤ m < n ≤ 100) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.

Output

For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with m vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.

Example

Input


2
6 3
7 3


Output


YES
NO

Note

<image> The first test case of the example 

It can be shown that the answer for the second test case of the example is "NO".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (int i = 0; i < (((int)(v).size())); ++i) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  return os << "(" << p.first << " " << p.second << ")";
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;
template <int64_t mod>
class modint {
  int64_t x;

 public:
  modint(int64_t x = 0) : x(x < 0 ? ((x % mod) + mod) % mod : x % mod) {}
  const modint operator-() const { return x == 0 ? 0 : mod - x; }
  modint& operator+=(const modint& rhs) {
    if ((x += rhs.x) >= mod) x -= mod;
    return *this;
  }
  modint& operator-=(const modint& rhs) { return *this += -rhs; }
  modint& operator*=(const modint& rhs) {
    (x *= rhs.x) %= mod;
    return *this;
  }
  modint& operator/=(const modint& rhs) { return *this *= rhs.pow(mod - 2); }
  friend const modint operator+(modint lhs, const modint& rhs) {
    return lhs += rhs;
  }
  friend const modint operator-(modint lhs, const modint& rhs) {
    return lhs -= rhs;
  }
  friend const modint operator*(modint lhs, const modint& rhs) {
    return lhs *= rhs;
  }
  friend const modint operator/(modint lhs, const modint& rhs) {
    return lhs /= rhs;
  }
  const modint pow(int64_t n) const {
    modint ret = 1, tmp = *this;
    while (n) {
      if (n & 1) ret *= tmp;
      tmp *= tmp;
      n >>= 1;
    }
    return ret;
  }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.x == rhs.x;
  }
  friend bool operator!=(const modint& lhs, const modint& rhs) {
    return lhs.x != rhs.x;
  }
  friend ostream& operator<<(ostream& os, const modint& a) { return os << a.x; }
  friend istream& operator>>(istream& is, modint& a) {
    int64_t tmp;
    is >> tmp;
    a = tmp;
    return is;
  }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int T;
  cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    cout << (n % m == 0 ? "YES" : "NO") << endl;
  }
  return 0;
}

```