#include <bits/stdc++.h>
using namespace std;
void Get(int &Ret) {
  char CH;
  bool FL = 0;
  for (; CH = getchar(), CH < '0' || CH > '9';)
    if (CH == '-') FL = 1;
  for (Ret = CH - '0'; CH = getchar(), CH >= '0' && CH <= '9';
       Ret = Ret * 10 + CH - '0')
    ;
  FL && (Ret = -Ret);
}
void Get(long long &Ret) {
  char CH;
  bool FL = 0;
  for (; CH = getchar(), CH < '0' || CH > '9';)
    if (CH == '-') FL = 1;
  for (Ret = CH - '0'; CH = getchar(), CH >= '0' && CH <= '9';
       Ret = Ret * 10 + CH - '0')
    ;
  FL && (Ret = -Ret);
}
const int MAXN = 110000;
const long long INF = 1234567890;
int n, m;
long long a[MAXN];
void Read() {
  int i;
  Get(n);
  Get(m);
  for (i = 1; i <= n; i++) Get(a[i]);
  sort(a + 1, a + n + 1);
}
map<long long, bool> is;
int que[MAXN], qcnt;
void Solve() {
  int i, cnt;
  for (i = 1; i <= n; i++) is[a[i]] = true;
  for (i = 1; i <= n; i++) {
    if (is[a[i]] == false) continue;
    cnt = 0;
    while (is[a[i]] == true) {
      is[a[i]] = false;
      a[i] *= m;
      cnt++;
    }
    que[++qcnt] = cnt;
  }
  cnt = 0;
  for (i = 1; i <= qcnt; i++) cnt += (que[i] - 1) / 2 + 1;
  printf("%d\n", cnt);
}
int main() {
  Read();
  Solve();
  return 0;
}

### Prompt

Please create a solution in cpp 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;
void Get(int &Ret) {
  char CH;
  bool FL = 0;
  for (; CH = getchar(), CH < '0' || CH > '9';)
    if (CH == '-') FL = 1;
  for (Ret = CH - '0'; CH = getchar(), CH >= '0' && CH <= '9';
       Ret = Ret * 10 + CH - '0')
    ;
  FL && (Ret = -Ret);
}
void Get(long long &Ret) {
  char CH;
  bool FL = 0;
  for (; CH = getchar(), CH < '0' || CH > '9';)
    if (CH == '-') FL = 1;
  for (Ret = CH - '0'; CH = getchar(), CH >= '0' && CH <= '9';
       Ret = Ret * 10 + CH - '0')
    ;
  FL && (Ret = -Ret);
}
const int MAXN = 110000;
const long long INF = 1234567890;
int n, m;
long long a[MAXN];
void Read() {
  int i;
  Get(n);
  Get(m);
  for (i = 1; i <= n; i++) Get(a[i]);
  sort(a + 1, a + n + 1);
}
map<long long, bool> is;
int que[MAXN], qcnt;
void Solve() {
  int i, cnt;
  for (i = 1; i <= n; i++) is[a[i]] = true;
  for (i = 1; i <= n; i++) {
    if (is[a[i]] == false) continue;
    cnt = 0;
    while (is[a[i]] == true) {
      is[a[i]] = false;
      a[i] *= m;
      cnt++;
    }
    que[++qcnt] = cnt;
  }
  cnt = 0;
  for (i = 1; i <= qcnt; i++) cnt += (que[i] - 1) / 2 + 1;
  printf("%d\n", cnt);
}
int main() {
  Read();
  Solve();
  return 0;
}

```