#include <bits/stdc++.h>
using namespace std;
struct Hp {
  const int oo = 1e9;
  int n;
  vector<int> mL, mR, d;
  vector<vector<int>> g;
  Hp(int n) : n(n), mL(n + 1), mR(n + 1), d(n + 1), g(n + 1) {}
  void edge(int u, int v) { g[u].push_back(v); }
  bool B() {
    queue<int> q;
    for (int u = 1; u <= n; u++)
      if (mL[u])
        d[u] = oo;
      else
        d[u] = 0, q.push(u);
    d[0] = oo;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[mR[v]] == oo) d[mR[v]] = d[u] + 1, q.push(mR[v]);
      }
    }
    return d[0] != oo;
  }
  bool D(int u) {
    if (!u) return 1;
    for (auto v : g[u])
      if (d[mR[v]] == d[u] + 1 && D(mR[v])) {
        mL[u] = v;
        mR[v] = u;
        return 1;
      }
    d[u] = oo;
    return false;
  }
  int A() {
    int r = 0;
    while (B())
      for (int u = 1; u <= n; u++)
        if (!mL[u] && D(u)) r++;
    return r;
  }
};
int arr[100007];
map<int, int> ase;
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  Hp bpm(n);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]), ase[arr[i]] = i;
  for (int i = 1; i <= n; i++)
    if ((long long)k * arr[i] <= 1000000000 and ase[k * arr[i]] and
        ase[k * arr[i]] != i)
      bpm.edge(i, ase[k * arr[i]]), bpm.edge(ase[k * arr[i]], i);
  int matched = bpm.A();
  printf("%d\n", n - matched / 2);
}

### Prompt

Please formulate a CPP solution to the following problem:

A k-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by k. That is, there are no two integers x and y (x < y) from the set, such that y = x·k.

You're given a set of n distinct positive integers. Your task is to find the size of it's largest k-multiple free subset.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109). The next line contains a list of n distinct positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

All the numbers in the lines are separated by single spaces.

Output

On the only line of the output print the size of the largest k-multiple free subset of {a1, a2, ..., an}.

Examples

Input

6 2
2 3 6 5 4 10


Output

3

Note

In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct Hp {
  const int oo = 1e9;
  int n;
  vector<int> mL, mR, d;
  vector<vector<int>> g;
  Hp(int n) : n(n), mL(n + 1), mR(n + 1), d(n + 1), g(n + 1) {}
  void edge(int u, int v) { g[u].push_back(v); }
  bool B() {
    queue<int> q;
    for (int u = 1; u <= n; u++)
      if (mL[u])
        d[u] = oo;
      else
        d[u] = 0, q.push(u);
    d[0] = oo;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[mR[v]] == oo) d[mR[v]] = d[u] + 1, q.push(mR[v]);
      }
    }
    return d[0] != oo;
  }
  bool D(int u) {
    if (!u) return 1;
    for (auto v : g[u])
      if (d[mR[v]] == d[u] + 1 && D(mR[v])) {
        mL[u] = v;
        mR[v] = u;
        return 1;
      }
    d[u] = oo;
    return false;
  }
  int A() {
    int r = 0;
    while (B())
      for (int u = 1; u <= n; u++)
        if (!mL[u] && D(u)) r++;
    return r;
  }
};
int arr[100007];
map<int, int> ase;
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  Hp bpm(n);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]), ase[arr[i]] = i;
  for (int i = 1; i <= n; i++)
    if ((long long)k * arr[i] <= 1000000000 and ase[k * arr[i]] and
        ase[k * arr[i]] != i)
      bpm.edge(i, ase[k * arr[i]]), bpm.edge(ase[k * arr[i]], i);
  int matched = bpm.A();
  printf("%d\n", n - matched / 2);
}

```