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

Difficulty: competition

Starter code:

Solutions:
n, k = map(int, input().split())
t = list(map(int, input().split()))
if k == 1: print(len(set(t)))
else:
    p = [set() for i in range(30)]
    for i in t:
        j = 0
        while i % k == 0:
            i //= k
            j += 1
        p[j].add(i)
    for j in range(1, 30):
        p[j] -= p[j - 1]
    print(sum(len(i) for i in p))

n, k = map(int, input().split())
t = list(map(int, input().split()))
if k == 1: print(len(set(t)))
else:
    p = [[] for i in range(30)]
    for i in t:
        j = 0
        while i % k == 0:
            i //= k
            j += 1
        p[j].append(i)
    p = [set(i) for i in p]
    for j in range(1, 30):
        p[j] -= p[j - 1]
    print(sum(len(i) for i in p))

n,k=list(map(int,input().split()))
L=list(map(int,input().split()))
L.sort(reverse=True)
S={}

for i in range(n):
    if(L[i]*k in S):
        continue
    S[L[i]]=1
print(len(S))


from sys import stdin

__author__ = 'artyom'


def read_next_line():
  return list(map(int, stdin.readline().strip().split()))


n, k = read_next_line()
a = read_next_line()
res = set(a)

if k > 1:
  excl = set()
  for x in reversed(sorted(a)):
    if x % k > 0 or x in excl:
      continue
    p = x / k
    if p in res:
      res.remove(p)
      excl.add(p)

print(len(res))

r=input("").split(' ')
x=int(r[0])
y=int(r[1])
l=input("").split(' ')
l=[int(x) for x in l]
l.sort()
k={}
r=len(l)
for g in range (len(l)):
    if (l[g]%y==0):
        rk=l[g]//y
        
        if (rk not in k):
            k[l[g]]=1
        else:
            r-=1
    else:
        k[l[g]]=1
print(r)

a, b=list(map(int, input().split(' ')))
ints=list(map(int, input().split(' ')))
ints.sort()

dictionary={}

for num in ints:
    if (num/b)%1!=0:
        dictionary[num] = 1
    else:
        if int(num/b) not in dictionary:
            dictionary[num]=1

print(len(dictionary))


n, k = map(int, input().split())
t = list(map(int, input().split()))
if k == 1:
    print(len(set(t)))
else:
    p = [set() for i in range(30)]
    for i in t:
        j = 0
        while i % k == 0:
            i //= k
            j += 1
        p[j].add(i)
    for j in range(1, 30):
        p[j] -= p[j - 1]
    print(sum(len(i) for i in p))

from sys import stdin

def main():
    '''
    Name: Kevin S. Sanchez
    Code: A. k-Multiple Free Set
    '''
    inp = stdin
    n, k = list(map(int, inp.readline().split()))
    nums = list(map(int, inp.readline().split()))
    nums.sort(reverse = True)
    # nums = set(nums)
    final = set()
    for i in range(0, n):
        mult = nums[i] * k
        if not(mult in final):
            final.add(nums[i])
    print(len(final))

main()


n, k = map(int, input().split())
arr = list(map(int, input().split()))
lol = {}
flag = {}
arr.sort()

for x in arr:
	flag[x] = 1

ans = 0
for i in range(len(arr)):
	if arr[i] in lol:
		continue
	
	cur = arr[i]
	cnt = 0

	while cur <= 1000000000:
		lol[cur] = 1
		if cur in flag:
			cnt += 1
		else:
			break
		cur = cur * k
		if k == 1:
			break

	ans += (cnt + 1) // 2
print(ans)

n, k = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()])
s = set(a)
l = 0
for x in a:
	t = 1
	while x in s:
		l += t
		t = 1 - t
		s.remove(x)
		x *= k
print(l)


def main():
    n, k = map(int, input().split())
    if n == 1:
        print(1)
        return
    l = sorted(map(int, input().split()))
    baned = set()
    s = set(l)
    if k > 1:
        for p in l:
            if p not in baned:
                p *= k
                s.discard(p)
                baned.add(p)
    print(len(s))


def __starting_point():
    main()
__starting_point()

'''def bSearch(a,x,n):
	low = 0
	high = n-1
	flag = False
	while(low <= high and flag == False):
		mid = (low+high)//2
		if(a[mid] == x):
			flag = True
		else:
			if(x < a[mid]):
				high = mid - 1
			else:
				low = mid + 1
	return flag

n,k = map(int,input().split())

a = list(map(int,input().split()))

s = []
m = 0
a = sorted(a)

for i in a:
	if(i % k != 0):
		s.append(i)
		m += 1
	elif(bSearch(s,i/k,m) == False):
		s.append(i)
		m += 1

print(m)
#print(s)'''

n,k = list(map(int,input().split()))

a = list(map(int,input().split()))
a = sorted(a)
s = []
d = {}
m = 0

for i in a:
	if(i % k != 0):
		s.append(i)
		m += 1
		d[i] = 1
	elif((i//k) not in d):
		s.append(i)
		d[i] = 1
		m += 1

print(m)
#print(d)
#print(s)


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lol = {}
flag = {}
arr.sort()

for x in arr:
	flag[x] = 1

ans = 0
for i in range(len(arr)):
	if arr[i] in lol:
		continue
	
	cur = arr[i]
	cnt = 0

	while cur <= 1000000000:
		lol[cur] = 1
		if cur in flag:
			cnt += 1
		else:
			break
		cur = cur * k
		if k == 1:
			break

	ans += (cnt + 1) // 2
print(ans)


# coding=utf-8
n, k = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a.sort()
s = []
d = {}
m = 0
for i in a:
    if i % k != 0:
        s.append(i)
        d[i] = 1
        m += 1
    elif (i // k) not in d:
        s.append(i)
        d[i] = 1
        m += 1
print(m)


import sys
k = int(sys.stdin.readline().split()[1])
t = list(map(lambda s: int(s), sys.stdin.readline().split()))
t.sort()
# print(t)
def find(x, a, b):
    while True:
        if a == b:
            if x == t[a]:
                return a
            else:
                return None
        m = a + (b - a) // 2
        if x > t[m]:
            a = m + 1
        else:
            b = m
u = [True for i in t]
s = 0
for i in range(len(t)):
    if u[i]:
        s += 1
        u[i] = False
        j = find(t[i] * k, 0, len(t) - 1)
        # print(t[i] * k, j)
        if j is not None:
            u[j] = False
print(s)

import sys
k = int(sys.stdin.readline().split()[1])
t = list(map(lambda s: int(s), sys.stdin.readline().split()))
t.sort()
# print(t)
def find(x, a, b):
    while True:
        if a == b:
            if x == t[a]:
                return a
            else:
                return None
        m = a + (b - a) // 2
        if x > t[m]:
            a = m + 1
        else:
            b = m
u = [True for i in t]
s = 0
for i in range(len(t)):
    if u[i]:
        s += 1
        u[i] = False
        j = find(t[i] * k, 0, len(t) - 1)
        # print(t[i] * k, j)
        if j is not None:
            u[j] = False
print(s)

def bSearch(x,li):
	l=0
	h=len(li)
	while(l<=h):
		m=(l+h)//2
		if(li[m]==x):
			return m
		elif(li[m]>x):
			h=m-1
		else:
			l=m+1
	return -1
n,k=list(map(int,input().split()))
li=list(map(int,input().split()))
li.sort()
s=set()
for i in range(n):
	if(li[i]%k==0):
		z = bSearch(li[i]//k,li)
		if(z!=-1):
			if li[z] not in s:
				s.add(li[i])
		else:
			s.add(li[i])
	else:
		s.add(li[i])
print(len(s))
		


n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
if k == 1:
	print(len(nums))
else:
	r = set()
	for i in sorted(nums):
		if i in r:
			continue
		else:
			r.add(i * k)
	print(len([i for i in nums if i not in r]))


n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
ans = set()
for i in arr:
    if i%k: ans.add(i)
    elif i//k not in ans: ans.add(i)
print(len(ans))


R = lambda: map(int, input().split())
n, k = R()
arr = sorted(list(R()))
s = set(arr)
if k == 1:
    print(n)
else:
    for x in arr:
        if x in s and x * k in s:
            s.remove(x * k)
    print(len(s))

# from itertools import combinations
# from bisect import bisect_left
# from functools import *
# from collections import Set

I = lambda: list(map(int, input().split()))
n, k = I()
a = sorted(I())
b = set(a)
if k != 1:
    for i in a:
        if i in b:
            b.discard(i*k)
print(len(b))

n,k=list(map(int,input().split()))

L=list(map(int,input().split()))

L.sort(reverse=True)

S={}



for i in range(n):

    if(L[i]*k in S):

        continue

    S[L[i]]=1

print(len(S))



n,k=map(int,input().split())
L=list(map(int,input().split()))
L.sort(reverse=True)
S={}

for i in range(n):
    if(L[i]*k in S):
        continue
    S[L[i]]=1
print(len(S))

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l=sorted(l)
ma=1
d={l[0]}
for i in range(1,n) :
    if l[i]/m not in d :
        d.add(l[i])
        ma+=1
print(ma)
              


n, k = list(map(int,input().split()))
ai = list(map(int,input().split()))
def binsearch(num):
    high = n-1
    low = 0
    mid = (high + low) // 2
    while high >= low:
        if ai[mid] < num:
            low = mid + 1
        elif ai[mid] > num:
            high = mid - 1
        else:
            return mid
        mid = (high + low) // 2
    return -1
ai.sort()
ar = [0]*n
ans = 0
for i in range(n):
    if ar[i]:
        continue
    num = binsearch(ai[i] * k)
    if num != -1:
        ar[num] = 1
        ans += 1
if k == 1:
    ans = 0
print(n - ans)