Given an array arr[] of N elements. Find the number of non-empty subsets whose product of elements is less than or equal to a given integer K. 
 
Example 1:
Input:
N = 4
arr[] = {2, 4, 5, 3}
K = 12
Output:
8
Explanation:
All possible subsets whose 
products are less than 12 are:
(2), (4), (5), (3), (2, 4), (2, 5), (2, 3), (4, 3)
Example 2:
Input:
N = 3
arr[] = {9, 8, 3}
K = 2 
Output:
0
Explanation:
There is no subsets with product less
than or equal to 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numOfSubsets() which takes 2 integers N, and K, and an array arr of size N as input and returns the number of subsets with product less equal to K.
Expected Time Complexity: O(N*2^{N/2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 30
1 ≤ arr[i] ≤ 10
1 ≤ K ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def numOfSubsets(self, arr, N, K):
        # code here 

Solutions:
class Solution:

	def f(self, arr, i, k, dp):
		if i < 0:
			if k > 0:
				return 1
			else:
				return 0
		if dp[i][k] != -1:
			return dp[i][k]
		nt = self.f(arr, i - 1, k, dp)
		t = 0
		if arr[i] <= k:
			t = self.f(arr, i - 1, k // arr[i], dp)
		dp[i][k] = t + nt
		return dp[i][k]

	def numOfSubsets(self, arr, n, k):
		dp = [[-1] * (k + 1) for _ in range(n + 1)]
		return self.f(arr, n - 1, k, dp) - 1


import bisect

class Solution:

	def calc(self, a, lo, hi, K):
		ans = []
		for i in range(1, 1 << hi - lo):
			temp = 1
			for j in range(lo, hi):
				if 1 << j - lo & i:
					temp *= a[j]
			if temp <= K:
				ans.append(temp)
		return ans

	def numOfSubsets(self, arr, N, K):
		left = self.calc(arr, 0, N // 2, K)
		right = self.calc(arr, N // 2, N, K)
		left.sort()
		ans = len(left) + len(right)
		for a in right:
			idx = bisect.bisect(left, K // a)
			ans += idx
		return ans


import bisect

class Solution:

	def numOfSubsets(self, arr, n, k):
		(vect1, vect2, subset1, subset2) = ([], [], [], [])
		for i in range(0, n):
			if arr[i] > k:
				continue
			if i <= n // 2:
				vect1.append(arr[i])
			else:
				vect2.append(arr[i])
		for i in range(0, 1 << len(vect1)):
			value = 1
			for j in range(0, len(vect1)):
				if i & 1 << j:
					value *= vect1[j]
			if value <= k:
				subset1.append(value)
		for i in range(0, 1 << len(vect2)):
			value = 1
			for j in range(0, len(vect2)):
				if i & 1 << j:
					value *= vect2[j]
			if value <= k:
				subset2.append(value)
		subset2.sort()
		count = 0
		for i in range(0, len(subset1)):
			count += bisect.bisect(subset2, k // subset1[i])
		count -= 1
		return count


import bisect

class Solution:

	def numOfSubsets(self, arr, n, req):
		(m, n) = ([], [])
		for i in range(len(arr)):
			if i <= len(arr) // 2:
				m.append(arr[i])
			else:
				n.append(arr[i])
		s1 = []
		s2 = []
		for i in range(1 << len(m)):
			p = 1
			for j in range(len(m)):
				if p > req:
					break
				if i >> j & 1:
					p *= m[j]
			if p <= req:
				s1.append(p)
		for i in range(1 << len(n)):
			p = 1
			for j in range(len(n)):
				if p > req:
					break
				if i >> j & 1:
					p *= n[j]
			if p <= req:
				s2.append(p)
		s2.sort()
		c = 0
		for i in range(len(s1)):
			c += bisect.bisect(s2, req // s1[i])
		return c - 1


class Solution:

	def numOfSubsets(self, arr, N, K):
		hmap = {}
		mod = 1000000000.0 + 7

		def count_prod(nums, prod, k, n):
			if n == 0:
				return 1 if prod <= k else 0
			if (prod, n) not in hmap:
				hmap[prod, n] = count_prod(nums, prod, k, n - 1) + count_prod(nums, prod * nums[n - 1], k, n - 1)
			return hmap[prod, n]
		ans = (count_prod(arr, 1, K, N) - 1) % mod
		return int(ans)


class Solution:

	def numOfSubsets(self, arr, N, K):
		d = dict()

		def dfs(arr, s1, k, i):
			if i == len(arr):
				if s1 <= k:
					return 1
				return 0
			if s1 > k:
				return 0
			if d.get((s1, i)) != None:
				return d[s1, i]
			d[s1, i] = dfs(arr, s1 * arr[i], k, i + 1) + dfs(arr, s1, k, i + 1)
			return d[s1, i]
		return dfs(arr, 1, K, 0) - 1


from functools import lru_cache
import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		(vect1, vect2, subset1, subset2) = ([], [], [], [])
		for i in range(0, N):
			if arr[i] > K:
				continue
			if i <= N // 2:
				vect1.append(arr[i])
			else:
				vect2.append(arr[i])
		for i in range(0, 1 << len(vect1)):
			value = 1
			for j in range(0, len(vect1)):
				if i & 1 << j:
					value *= vect1[j]
			if value <= K:
				subset1.append(value)
		for i in range(0, 1 << len(vect2)):
			value = 1
			for j in range(0, len(vect2)):
				if i & 1 << j:
					value *= vect2[j]
			if value <= K:
				subset2.append(value)
		subset2.sort()
		count = 0
		for i in range(0, len(subset1)):
			count += bisect.bisect(subset2, K // subset1[i])
		count -= 1
		return count


from bisect import bisect_right as upper

class Solution:

	def createSubsets(self, a, products):
		arr_len = len(a)
		total = 1 << arr_len
		for i in range(0, total):
			product = 1
			for j in range(0, arr_len):
				if i & 1 << j:
					product *= a[j]
			products.append(product)

	def numOfSubsets(self, arr, N, K):
		arr1 = []
		arr2 = []
		for i in range(0, N):
			if i < N // 2:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
		products1 = []
		products2 = []
		self.createSubsets(arr1, products1)
		self.createSubsets(arr2, products2)
		products2.sort()
		cnt = 0
		for prod in products1:
			cnt += upper(products2, K // prod)
		return cnt - 1


import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		res = 0
		subset1 = []
		subset2 = []
		for i in range(N):
			if arr[i] > K:
				continue
			elif i < N // 2:
				subset1.append(arr[i])
			else:
				subset2.append(arr[i])
		(prd1, prd2) = ([], [])
		for i in range(1 << len(subset1)):
			value = 1
			for j in range(len(subset1)):
				if i & 1 << j:
					value *= subset1[j]
			if value <= K:
				prd1.append(value)
		for i in range(1 << len(subset2)):
			value = 1
			for j in range(len(subset2)):
				if i & 1 << j:
					value *= subset2[j]
			if value <= K:
				prd2.append(value)
		prd2.sort()
		for i in range(len(prd1)):
			res += bisect.bisect(prd2, K // prd1[i])
		res -= 1
		return res


class Solution:

	def recursion_loop(self, arr, K):
		if (tuple(arr), K) in self.cache:
			return self.cache[tuple(arr), K]
		arr = [a for a in arr if a <= K]
		n = len(arr)
		if n <= 1:
			return n
		arr.sort()
		num_subsets = n
		i = 0
		while i < len(arr) - 1:
			a = arr[i]
			if a * arr[i + 1] > K:
				break
			if i == len(arr) - 2:
				num_subsets += 1
				break
			while arr[-1] * a > K:
				arr.pop()
			num_subsets += self.recursion_loop(arr[i + 1:], K // a)
			i += 1
		self.cache[tuple(arr), K] = num_subsets
		return num_subsets

	def numOfSubsets(self, arr, N, K):
		self.cache = {}
		return self.recursion_loop(arr, K)


import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		sub1 = []
		sub2 = []
		solve(arr[:N // 2], [], K, sub1)
		solve(arr[N // 2:], [], K, sub2)
		sub1.sort()
		sub2.sort()
		ans = len(sub1) + len(sub2)
		for i in range(len(sub1)):
			val = K // sub1[i]
			idx = bisect.bisect_right(sub2, val)
			ans += idx
		return ans

def solve(que, ans, k, sub):
	if not que:
		prod = findp(ans)
		if prod <= k and ans:
			sub.append(prod)
		return
	char = que[0]
	que = que[1:]
	solve(que, ans + [char], k, sub)
	solve(que, ans, k, sub)

def findp(arr):
	p = 1
	for i in arr:
		p *= i
	return p


class Solution:

	def numOfSubsets(self, arr, N, K):
		arr.sort()
		answer = [-1]
		dp = dict()

		def rec(prod, ind):
			if prod > K:
				return 0
			if ind == N:
				if prod <= K:
					return 1
				return
			if (prod, ind) not in dp:
				val = prod * arr[ind]
				ans = rec(val, ind + 1) + rec(prod, ind + 1)
				dp[prod, ind] = ans
			return dp[prod, ind]
		return rec(1, 0) - 1
		return answer[0]


from bisect import *

class Solution:

	def numOfSubsets(self, arr, N, K):

		def get_subsets(arr):
			n = len(arr)
			ans = []
			for i in range(1, 1 << n):
				cur = 1
				for j in range(n):
					if i & 1 << j:
						cur *= arr[j]
				if cur <= K:
					ans.append(cur)
			return sorted(ans)
		x = N // 2
		arr1 = get_subsets(arr[:x])
		arr2 = get_subsets(arr[x:])
		ans = len(arr1) + len(arr2)
		for i in arr1:
			x = K // i
			ans += bisect_right(arr2, x)
		return ans


class Solution:

	def numOfSubsets(self, arr, N, K):
		dp = {}

		def recur(i, prod):
			if i == N:
				return 1
			if (i, prod) in dp:
				return dp[i, prod]
			(ch1, ch2, ch3) = (0, 0, 0)
			if prod * arr[i] <= K:
				ch1 = recur(i + 1, prod * arr[i])
				ch2 = recur(i + 1, prod)
			else:
				ch3 = recur(i + 1, prod)
			dp[i, prod] = ch1 + ch2 + ch3
			return dp[i, prod]
		return recur(0, 1) - 1


class Solution:

	def nos(self, arr, N, K, idx, product, hm):
		if idx == N:
			if product <= K:
				return 1
			return 0
		if product > K:
			return 0
		if hm.get(product * 100 + idx):
			return hm[product * 100 + idx]
		a = self.nos(arr, N, K, idx + 1, product * arr[idx], hm)
		b = self.nos(arr, N, K, idx + 1, product, hm)
		hm[product * 100 + idx] = a + b
		return a + b

	def numOfSubsets(self, arr, N, K):
		hm = {}
		product = 1
		idx = 0
		product = 1
		c = self.nos(arr, N, K, idx, product, hm)
		return c - 1


class Solution:

	def util(self, A, start, N, K, prod, T):
		if prod > K:
			return 0
		if start == N:
			if prod <= K:
				return 1
			else:
				return 0
		if T[start][prod] != -1:
			return T[start][prod]
		else:
			T[start][prod] = self.util(A, start + 1, N, K, prod * A[start], T) + self.util(A, start + 1, N, K, prod, T)
			return T[start][prod]

	def numOfSubsets(self, A, N, K):
		T = [[-1] * (K + 1) for i in range(N + 1)]
		start = 0
		prod = 1
		return self.util(A, start, N, K, prod, T) - 1


class Solution:

	def numOfSubsets(self, arr, N, K):

		def recur(arr, i, pro, K, dp):
			if i == 0:
				if pro <= K:
					return 1
				return 0
			if pro > K:
				return 0
			if dp[i][pro] != -1:
				return dp[i][pro]
			a = recur(arr, i - 1, pro, K, dp)
			b = recur(arr, i - 1, pro * arr[i - 1], K, dp)
			dp[i][pro] = a + b
			return a + b
		dp = [[-1] * (K + 1) for _ in range(N + 1)]
		return recur(arr, N, 1, K, dp) - 1


class Solution:

	def numOfSubsets(self, x, n, k):
		dp = {}

		def f(i, j):
			if j > k:
				return 0
			if i == n:
				return 1
			if (i, j) in dp:
				return dp[i, j]
			dp[i, j] = f(i + 1, j) + f(i + 1, j * x[i])
			return dp[i, j]
		return f(0, 1) - 1


import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		(vect1, vect2, subset1, subset2) = ([], [], [], [])
		for i in range(0, N):
			if arr[i] > K:
				continue
			if i <= N // 2:
				vect1.append(arr[i])
			else:
				vect2.append(arr[i])
		for i in range(0, 1 << len(vect1)):
			value = 1
			for j in range(0, len(vect1)):
				if i & 1 << j:
					value *= vect1[j]
			if value <= K:
				subset1.append(value)
		for i in range(0, 1 << len(vect2)):
			value = 1
			for j in range(0, len(vect2)):
				if i & 1 << j:
					value *= vect2[j]
			if value <= K:
				subset2.append(value)
		subset2.sort()
		count = 0
		for i in range(0, len(subset1)):
			count += bisect.bisect(subset2, K // subset1[i])
		count -= 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(int, input().split()))
		K = int(input())
		ob = Solution()
		print(ob.numOfSubsets(arr, N, K))


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def numOfSubsets(self, arr, n, k):
		d = {}

		def solve(i, pd):
			if pd > k:
				return 0
			if i == n:
				return 1
			if d.get((i, pd)):
				return d[i, pd]
			d[i, pd] = solve(i + 1, pd * arr[i]) + solve(i + 1, pd)
			return d[i, pd]
		return solve(0, 1) - 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(int, input().split()))
		K = int(input())
		ob = Solution()
		print(ob.numOfSubsets(arr, N, K))


class Solution:

	def numOfSubsets(self, l, n, k):
		(l1, l2, s1, s2) = ([], [], [], [])
		for i in range(0, n):
			if l[i] > k:
				continue
			if i <= n // 2:
				l1.append(l[i])
			else:
				l2.append(l[i])
		for i in range(0, 1 << len(l1)):
			value = 1
			for j in range(0, len(l1)):
				if i & 1 << j:
					value *= l1[j]
			if value <= k:
				s1.append(value)
		for i in range(0, 1 << len(l2)):
			value = 1
			for j in range(0, len(l2)):
				if i & 1 << j:
					value *= l2[j]
			if value <= k:
				s2.append(value)
		s2.sort()

		def ss(x):
			i = 0
			j = len(s2) - 1
			ans = 0
			if x >= s2[-1]:
				return len(s2)
			if x < s2[0]:
				return 0
			while i <= j:
				m = (i + j) // 2
				if s2[m] <= x:
					ans = m
					i = m + 1
				else:
					j = m - 1
			return ans + 1
		ans = -1
		for i in s1:
			ans += ss(k // i)
		return ans


class Solution:

	def numOfSubsets(self, arr, N, K):
		arr.sort()
		ans = {}

		def fun(index, k):
			if (index, k) in ans:
				return ans[index, k]
			if index == 0:
				return 1 if arr[index] <= k else 0
			result = 1 if arr[index] <= k else 0
			result += fun(index - 1, k)
			result += fun(index - 1, k / arr[index]) if k >= arr[index] else 0
			ans[index, k] = result
			return result
		return fun(N - 1, K)


import bisect

class Solution:

	def createsubset(self, sub, arr):
		n = len(arr)
		total_subsets = 2 ** n
		for i in range(0, total_subsets):
			product = 1
			for j in range(0, n):
				if i & 1 << j != 0:
					product = product * arr[j]
			sub.append(product)

	def numOfSubsets(self, arr, n, k):
		arr1 = []
		arr2 = []
		for i in range(n):
			if i < n // 2:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
		sub1 = []
		sub2 = []
		self.createsubset(sub1, arr1)
		self.createsubset(sub2, arr2)
		sub2.sort()
		position = 0
		for i in sub1:
			position += bisect.bisect(sub2, k // i)
		position -= 1
		return position


import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		(arr1, arr2) = ([], [])
		for i in range(N):
			if arr[i] > K:
				continue
			elif i <= N // 2:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
		(sset1, sset2) = ([], [])
		for i in range(1 << len(arr1)):
			val = 1
			for j in range(len(arr1)):
				if i & 1 << j:
					val *= arr1[j]
			if val <= K:
				sset1.append(val)
		for i in range(1 << len(arr2)):
			val = 1
			for j in range(len(arr2)):
				if i & 1 << j:
					val *= arr2[j]
			if val <= K:
				sset2.append(val)
		sset2.sort()
		cnt = 0
		for i in range(len(sset1)):
			cnt += bisect.bisect(sset2, K // sset1[i])
		cnt -= 1
		return cnt


import bisect

def prod(arr):
	prod = 1
	for i in arr:
		prod *= i
	return prod

def getSubsetProds(arr, k):
	if len(arr) == 0:
		return []
	if len(arr) == 1:
		ret = arr
	a = arr.pop()
	s1 = [a]
	s2 = getSubsetProds(arr, k)
	subs = s1 + s2 + [a * s for s in s2]
	return list(filter(lambda x: x <= k, subs))

class Solution:

	def numOfSubsets(self, arr, N, K):
		mid = int(N / 2)
		left_subprods = [1] + sorted(getSubsetProds(arr[:mid], K))
		right_subprods = [1] + sorted(getSubsetProds(arr[mid:], K))
		nsets = 0
		for i in range(0, len(left_subprods)):
			nsets += bisect.bisect(right_subprods, K // left_subprods[i])
		return nsets - 1


import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		(vect1, vect2, subset1, subset2) = ([], [], [], [])
		for i in range(0, N):
			if arr[i] > K:
				continue
			if i <= N // 2:
				vect1.append(arr[i])
			else:
				vect2.append(arr[i])
		n1 = len(vect1)
		n2 = len(vect2)
		for i in range(0, 1 << n1):
			val = 1
			for j in range(0, n1):
				if i & 1 << j:
					val *= vect1[j]
			if val <= K:
				subset1.append(val)
		for i in range(0, 1 << n2):
			val = 1
			for j in range(0, n2):
				if i & 1 << j:
					val *= vect2[j]
			if val <= K:
				subset2.append(val)
		subset2.sort()
		count = 0
		for i in range(0, len(subset1)):
			count += bisect.bisect(subset2, K // subset1[i])
		count -= 1
		return count


class Solution:

	def numOfSubsets(self, arr, N, K):
		arr.sort()
		self.res = 0
		cache = {}

		def mySol(ind, product):
			if (ind, product) in cache:
				return cache[ind, product]
			if ind >= N:
				return 1
			res = 0
			if arr[ind] * product <= K:
				res += mySol(ind + 1, product * arr[ind])
			res += mySol(ind + 1, product)
			cache[ind, product] = res
			return res
		return mySol(0, 1) - 1


class Solution:

	def numOfSubsets(self, arr, N, K):

		def helper(prod, i):
			nonlocal ans, memo
			if prod <= K and i == N:
				return 1
			if prod > K or i == N:
				return 0
			key = (prod, i)
			if key in memo:
				return memo[key]
			memo[key] = helper(prod * arr[i], i + 1) + helper(prod, i + 1)
			return memo[key]
		memo = {}
		ans = helper(1, 0)
		return ans - 1


class Solution:

	def numOfSubsets(self, arr, N, K):
		memo = {}

		def dp(i, prod):
			if prod > K:
				return -1
			if i == N:
				return 0
			if (i, prod) in memo:
				return memo[i, prod]
			ans = 1 + dp(i + 1, prod * arr[i]) + dp(i + 1, prod)
			memo[i, prod] = ans
			return ans
		return dp(0, 1)


import functools

class Solution:

	def numOfSubsets(self, arr, N, K):

		@functools.lru_cache(maxsize=None)
		def calc(i, k):
			if i < 0:
				return 1
			if arr[i] > k:
				return calc(i - 1, k)
			return calc(i - 1, k) + calc(i - 1, k // arr[i])
		return calc(N - 1, K) - 1


class Solution:

	def numOfSubsets(self, arr, N, K):
		memo = {}

		def calc(i, k):
			if i < 0:
				return 1
			if (i, k) in memo:
				return memo[i, k]
			if arr[i] > k:
				memo[i, k] = calc(i - 1, k)
				return memo[i, k]
			memo[i, k] = calc(i - 1, k) + calc(i - 1, k // arr[i])
			return memo[i, k]
		return calc(N - 1, K) - 1


import bisect

class Solution:

	def numOfSubsets(self, arr, n, k):

		def solve(vect, subset, res, i):
			if i >= len(vect):
				return
			if vect[i] * res <= k:
				subset.append(vect[i] * res)
				solve(vect, subset, res * vect[i], i + 1)
			solve(vect, subset, res, i + 1)
		(vect1, vect2, subset1, subset2) = ([], [], [], [])
		for i in range(0, n):
			if arr[i] > k:
				continue
			if i <= n // 2:
				vect1.append(arr[i])
			else:
				vect2.append(arr[i])
		solve(vect1, subset1, 1, 0)
		solve(vect2, subset2, 1, 0)
		subset1.insert(0, 1)
		subset2.append(1)
		subset2.sort()
		count = 0
		for i in range(0, len(subset1)):
			count += bisect.bisect(subset2, k // subset1[i])
		count -= 1
		return count


from bisect import bisect

class Solution:

	def products(self, arr, k):
		products = [1]
		for x in arr:
			products.extend([x * y for y in products if x * y <= k])
		return sorted(products[1:])

	def max_index(self, f, arr, min, max):
		if min + 1 == max:
			return min if f(arr[min]) else -1
		mid = (min + max) // 2
		return self.max_index(f, arr, mid, max) if f(arr[mid]) else self.max_index(f, arr, min, mid)

	def numOfSubsets(self, arr, n, k):
		arr = [a for a in arr if a <= k]
		if n <= 1:
			return n
		n2 = n // 2
		count = self.numOfSubsets(arr[:n2], len(arr[:n2]), k) + self.numOfSubsets(arr[n2:], len(arr[n2:]), k)
		products = self.products(arr[n2:], k)
		for x in self.products(arr[:n2], k):
			count += 1 + self.max_index(lambda y: x * y <= k, products, 0, len(products))
		return count


from bisect import bisect

class Solution:

	def products(self, arr, k):
		products = [1]
		for x in arr:
			products.extend([x * y for y in products if x * y <= k])
		return sorted(products[1:])

	def search_index(self, f, products, min, max):
		if min + 1 == max:
			return min if f(products[min]) else max
		else:
			mid = (min + max) // 2
			return self.search_index(f, products, min, mid) if f(products[mid]) else self.search_index(f, products, mid, max)

	def numOfSubsets(self, arr, n, k):
		arr = [a for a in arr if a <= k]
		if n <= 1:
			return n
		left = arr[:n // 2]
		right = arr[n // 2:]
		count = self.numOfSubsets(left, len(left), k) + self.numOfSubsets(right, len(right), k)
		left_products = self.products(left, k)
		right_products = self.products(right, k)
		for left_product in left_products:
			count += self.search_index(lambda right_product: left_product * right_product > k, right_products, 0, len(right_products))
		return count


from bisect import bisect

class Solution:

	def products(self, arr, k):
		products = [1]
		for x in arr:
			products.extend([x * y for y in products if x * y <= k])
		return sorted(products[1:])

	def numOfSubsets(self, arr, n, k):
		arr = [a for a in arr if a <= k]
		if n <= 1:
			return n
		left = arr[:n // 2]
		right = arr[n // 2:]
		count = self.numOfSubsets(left, len(left), k) + self.numOfSubsets(right, len(right), k)
		left_products = self.products(left, k)
		right_products = self.products(right, k)
		for p in left_products:
			count += bisect(right_products, k // p)
		return count


from bisect import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		if N == 0:
			return 0
		if N == 1:
			return 1 if arr[0] <= K else 0
		N2 = N // 2
		arr1 = [a for (i, a) in enumerate(arr) if i < N2 and a <= K]
		arr2 = [a for (i, a) in enumerate(arr) if i >= N2 and a <= K]
		count = self.numOfSubsets(arr1, len(arr1), K) + self.numOfSubsets(arr2, len(arr2), K)
		prod1 = [1]
		while len(arr1) > 0:
			a1 = arr1.pop()
			prod1 = [*prod1, *[a1 * a for a in prod1 if a1 * a <= K]]
		prod1 = sorted(prod1[1:])
		prod2 = [1]
		while len(arr2) > 0:
			a2 = arr2.pop()
			prod2 = [*prod2, *[a2 * a for a in prod2 if a2 * a <= K]]
		prod2 = sorted(prod2[1:])
		for i in range(0, len(prod1)):
			count += bisect(prod2, K // prod1[i])
		return count


ans = 0

def mgc(arr, k, p, i, dp):
	if i < 0:
		if p <= k:
			return 1
		return 0
	if (i, p) in dp:
		return dp[i, p]
	dp[i, p] = mgc(arr, k, p * arr[i], i - 1, dp) + mgc(arr, k, p, i - 1, dp)
	return dp[i, p]

class Solution:

	def numOfSubsets(self, arr, N, K):
		global ans
		ans = 0
		dp = {}
		return mgc(arr, K, 1, N - 1, dp) - 1


from bisect import bisect

class Solution:

	def numOfSubsets(self, arr, N, K):
		(l1, l2, prod1, prod2) = ([], [], [], [])
		mid = N // 2
		for i in range(mid):
			if arr[i] > K:
				continue
			l1.append(arr[i])
		for i in range(mid, N):
			if arr[i] > K:
				continue
			l2.append(arr[i])
		for i in range(pow(2, len(l1))):
			val = 1
			for j in range(len(l1)):
				if i & 1 << j:
					val *= l1[j]
			if val <= K:
				prod1.append(val)
		for i in range(pow(2, len(l2))):
			val = 1
			for j in range(len(l2)):
				if i & 1 << j:
					val *= l2[j]
			if val <= K:
				prod2.append(val)
		prod2.sort()
		count = 0
		for i in prod1:
			count += bisect(prod2, K // i)
		return count - 1