No tag edit access

A. k-Multiple Free Set

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA *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* ≤ 10^{5}, 1 ≤ *k* ≤ 10^{9}). The next line contains a list of *n* distinct positive integers *a* _{1}, *a* _{2}, ..., *a* _{ n} (1 ≤ *a* _{ i} ≤ 10^{9}).

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 {*a* _{1}, *a* _{2}, ..., *a* _{ n}}.

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}.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/15/2020 23:18:01 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|