A number is called powerful if it is a power of two or a factorial. In other words, the number $m$ is powerful if there exists a non-negative integer $d$ such that $m=2^d$ or $m=d!$, where $d!=1\cdot 2\cdot \ldots \cdot d$ (in particular, $0! = 1$). For example $1$, $4$, and $6$ are powerful numbers, because $1=1!$, $4=2^2$, and $6=3!$ but $7$, $10$, or $18$ are not.

You are given a positive integer $n$. Find the minimum number $k$ such that $n$ can be represented as the sum of $k$ distinct powerful numbers, or say that there is no such $k$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

A test case consists of only one line, containing one integer $n$ ($1\le n\le 10^{12}$).


-----Output-----

For each test case print the answer on a separate line.

If $n$ can not be represented as the sum of distinct powerful numbers, print $-1$.

Otherwise, print a single positive integer  — the minimum possible value of $k$.


-----Examples-----

Input
4
7
11
240
17179869184
Output
2
3
4
1


-----Note-----

In the first test case, $7$ can be represented as $7=1+6$, where $1$ and $6$ are powerful numbers. Because $7$ is not a powerful number, we know that the minimum possible value of $k$ in this case is $k=2$.

In the second test case, a possible way to represent $11$ as the sum of three powerful numbers is $11=1+4+6$. We can show that there is no way to represent $11$ as the sum of two or less powerful numbers.

In the third test case, $240$ can be represented as $240=24+32+64+120$. Observe that $240=120+120$ is not a valid representation, because the powerful numbers have to be distinct.

In the fourth test case, $17179869184=2^{34}$, so $17179869184$ is a powerful number and the minimum $k$ in this case is $k=1$.

Difficulty: MEDIUM
Tags: Bit manipulation

Constructive algorithms

Complete search

Dynamic programming

Mathematics
Skill types: Dynamic programming

Bit manipulation

Complete search

Starter code:

Solutions:
def get(good):
	n = int(input())
	ans = 10000.0
	for x in good:
		if n >= x[0]:
			rem = n - x[0]
			ans = min(ans, x[1] + bin(rem).count('1'))
	print(ans)
good = [(0, 0)]
fact = []
c = 2
for i in range(3, 15):
	c *= i
	fact.append(c)
for f in fact:
	good_no = []
	for num in good:
		good_no.append((num[0] + f, num[1] + 1))
	good.extend(good_no)
for _ in range(int(input())):
	get(good)


from math import factorial
from itertools import combinations
facts = []
for i in range(3, 15):
	facts.append(factorial(i))
combs = []
for i in range(15):
	for k in combinations(facts, i):
		combs.append([len(k), sum(k)])
t = int(input())
for _ in range(t):
	x = int(input())
	res = []
	for (cnt, num) in combs:
		left = x - num
		if left >= 0:
			b = bin(left)
			res.append(cnt + b.count('1'))
	print(min(res))


from math import factorial
from itertools import combinations
facts = []
for i in range(3, 15):
	facts.append(factorial(i))
combs = []
for i in range(15):
	for j in combinations(facts, i):
		combs.append([len(j), sum(j)])
tc = int(input())
for j in range(tc):
	x = int(input())
	list3 = []
	for (i, k) in combs:
		if x - k >= 0:
			b = bin(x - k)
			list3.append(i + b.count('1'))
	print(min(list3))


lm = int(1000000000000.0)
f = [1]
for i in range(2, 17):
	if f[-1] * i < lm:
		f.append(f[-1] * i)
d = []

def t(i, nb, s):
	if i == 12:
		if s < lm and bin(s).count('1') - nb > 0:
			d.append([s, nb])
	else:
		t(i + 1, nb, s)
		t(i + 1, nb + 1, s + f[i])
f = f[2:]
t(0, 0, 0)
d = sorted(d, key=lambda x: x[0])
for _ in range(int(input())):
	n = int(input())
	ans = bin(n).count('1')
	for e in d:
		if e[0] <= n:
			ans = min(ans, e[1] + bin(n - e[0]).count('1'))
		else:
			break
	print(ans)


from itertools import combinations
from math import factorial
facs = [factorial(x) for x in range(3, 15)]
for _ in range(int(input())):
	n = int(input())
	ans = 40
	for x in range(12):
		for comb in combinations(facs, x):
			now = sum(comb)
			if now <= n:
				temp = n - now
				co = x + bin(temp).count('1')
				if co < ans:
					ans = co
	print(ans)


from collections import deque
powerful = [1]
for i in range(2, 16):
	powerful.append(i * powerful[-1])
powerful.append(4)
for i in range(3, 41):
	powerful.append(2 * powerful[-1])
powerful.sort(reverse=True)
for tcase in range(int(input())):
	q = deque()
	(n, k, i) = (int(input()), 0, 0)
	while n > 0:
		while i < len(powerful) and powerful[i] > n:
			i += 1
		while i < len(powerful) and n - powerful[i] < 2 * powerful[i]:
			q.append((n - powerful[i], k + 1, i + 1))
			i += 1
		(n, k, i) = q.popleft()
	print(k)


from math import factorial
fact_sum = {}

def solve(n):
	ans = 10 ** 12
	for (k, v) in fact_sum.items():
		if n >= v:
			ans = min(ans, bin(k).count('1') + bin(n - v).count('1'))
	print(ans)

def precalcualte():
	FACT = 14
	factorials = []
	f = 1
	for n in range(1, FACT + 1):
		f *= n
		if f >= 2:
			factorials.append(f)
	for i in range(1 << len(factorials)):
		s = 0
		for j in range(len(factorials)):
			if i & 1 << j:
				s += factorials[j]
		fact_sum[i] = s
precalcualte()
t = input().strip()
for i in range(int(t)):
	n = input().strip()
	solve(int(n))


import math
import itertools
facts = []
for i in range(3, 16):
	facts.append(math.factorial(i))
combs = []
for i in range(16):
	c = list(itertools.combinations(facts, i))
	for k in c:
		combs.append(k)
sums = []
for i in range(len(combs)):
	sums.append([sum(combs[i]), len(combs[i])])
t = int(input())
for i in range(t):
	itchislo = 0
	minsum = 1000000000000000
	sum1 = 0
	n = int(input())
	j = 0
	while j < len(sums):
		if n - sums[j][0] < 0:
			j += 1
			continue
		else:
			sum1 = 0
			itchislo = n - sums[j][0]
			itchislo = bin(itchislo)
			itchislo = itchislo[2:]
			sum1 += itchislo.count('1')
			sum1 += sums[j][1]
			if minsum > sum1:
				minsum = sum1
		j += 1
	print(minsum)


from math import factorial
from itertools import combinations
from sys import stdin
input = stdin.readline

def main():
	fact = [factorial(i) for i in range(1, 16)]
	combi = []
	for i in range(0, 16):
		for element in combinations(fact, i):
			combi.append([len(element), sum(element)])
	for _ in range(int(input())):
		n = int(input())
		total_terms = []
		for (a, b) in combi:
			remain = n - b
			if remain >= 0:
				no_1 = bin(remain).count('1')
				total_terms.append(a + no_1)
		print(min(total_terms))
main()


from itertools import combinations

def bit_count(value: int) -> int:
	return f'{value:b}'.count('1')
factorial = [1]
for _ in range(int(input())):
	n = int(input())
	while factorial[-1] <= n:
		factorial.append(factorial[-1] * len(factorial))
	factorial.pop()
	result = float('inf')
	for i in range(len(factorial) - 2):
		for combination in combinations(factorial[2:], i):
			if '1' in combination or '2' in combination:
				continue
			value = n - sum(combination)
			if value < 0:
				continue
			result = min(result, i + bit_count(value))
	if result == float('inf'):
		result = 1
	print(result)


def count(n, id):
	if n == 0:
		return 0
	min_ = bin(n).count('1')
	i = 0
	while f[i] <= n and i < id:
		min_ = min(min_, count(n - f[i], i) + 1)
		i += 1
	return min_
f = [1]
i = 2
while f[-1] < 10 ** 12:
	f.append(f[-1] * i)
	i += 1
for t in range(int(input())):
	print(count(int(input()), 20))


def factorials(n):
	factorials_list = []
	prod = 6
	i = 4
	while prod <= n:
		factorials_list.append(prod)
		prod *= i
		i += 1
	return factorials_list

def count(a):
	ans = 9223372036854775807
	for mask in range(1 << len(a)):
		s = n
		for i in range(len(a)):
			s -= [0, a[i]][mask & 1 << i != 0]
		if s < 0:
			continue
		ans = min(bin(mask).count('1') + bin(s).count('1'), ans)
	return ans
for _ in range(int(input())):
	n = int(input())
	a = factorials(n)
	print(count(a))


from math import *
from itertools import *
fact = [factorial(i) for i in range(15)]
comb = [(i, sum(s)) for i in range(15) for s in combinations(fact, i)]
for i in range(int(input())):
	num = int(input())
	print(min((i + bin(num - j).count('1') for (i, j) in comb if j <= num)))


fact = [1] * 15
subs = []
for i in range(1, 15):
	fact[i] = fact[i - 1] * (i + 1)
for i in range(1 << 15):
	(sub, s) = (0, 0)
	for j in range(15):
		if i & 1 << j:
			sub += 1
			s += fact[j]
	subs.append((sub, s))
for _ in range(int(input())):
	n = int(input())
	ans = bin(n).count('1')
	for i in subs:
		if i[1] <= n:
			ans = min(ans, i[0] + bin(n - i[1]).count('1'))
	print(ans)


from itertools import *
a = (1,)
r = range(14)
for i in r:
	a += (a[-1] * (i + 1),)
b = [(i, sum(c)) for i in r for c in combinations(a, i)]
for n in [*map(int, open(0))][1:]:
	print(min((m + bin(n - s).count('1') for (m, s) in b if s <= n)))
lst = []


a = []
p = 1
for i in range(1, 15):
	p *= i
	if bin(p).count('1') > 1:
		a.append(p)
T = int(input())
for t in range(T):
	n = int(input())
	ans = 10000000000
	if n & n - 1 == 0 or n in a:
		print(1)
		continue
	for i in range(1 << 12):
		s = 0
		for j in range(12):
			if i & 1 << j:
				s += a[j]
		if s > n:
			break
		ans = min(ans, bin(i).count('1') + bin(n - s).count('1'))
	print(ans)


from collections import *
fact = [1]
power = [1]
for i in range(1, 20):
	fact.append(fact[-1] * i)
	power.append(power[-1] * 2)

def count_bit(num):
	return str(bin(num)).count('1')
d = defaultdict(lambda : -1)

def f(i, target):
	if target == 0:
		return 0
	if target < 0 or i > 15:
		return float('inf')
	if d[i, target] != -1:
		return d[i, target]
	d[i, target] = min(1 + f(i + 1, target - fact[i]), f(i + 1, target), count_bit(target))
	return d[i, target]
for _ in range(int(input())):
	n = int(input())
	print(f(3, n))


from math import *
from itertools import combinations
fact = [factorial(x) for x in range(15)]
comb = [(i, sum(x)) for i in range(15) for x in combinations(fact, i)]
for t in range(int(input())):
	n = int(input())
	print(min((i + bin(n - x).count('1') for (i, x) in comb if x <= n)))


(k, idx) = (2, 3)
fact = []
while k <= 1000000000000.0:
	k *= idx
	fact.append(k)
	idx += 1

def fac(x):
	for i in range(len(fact)):
		if fact[i] > x:
			return i
for _ in range(int(input())):
	n = int(input())
	i = fac(n)
	ans = min(1000000000000000.0, bin(n).count('1'))
	for j in range(1 << i):
		s = 0
		a1 = 0
		for k in range(i):
			if 1 << k & j:
				s += fact[k]
				a1 += 1
		dif = n - s
		if dif >= 0:
			ans = min(ans, a1 + bin(dif).count('1'))
	print(ans)


import math
a = [6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200]
for t in range(int(input())):
	n = int(input())
	res = bin(n).count('1')
	if math.log(n, 2) == int(math.log(n, 2)) or n in a:
		print(1)
		continue
	for i in range(1, 4096):
		s = 0
		for j in range(12):
			if i & 1 << j:
				s += a[j]
		if s > n:
			break
		res = min(res, bin(i).count('1') + bin(n - s).count('1'))
	print(res)


from itertools import combinations
from sys import stdin
input = stdin.readline
l = []
a = 1
for i in range(1, 15):
	a *= i
	l.append(a)
for _ in range(int(input())):
	n = int(input())
	r = 100
	for i in range(15):
		for j in combinations(l, i):
			s = n - sum(j)
			if s >= 0:
				r = min(r, i + bin(s).count('1'))
	print(r)


from math import factorial

def bit_count(x):
	return bin(x).count('1')

def solve_task(n, ps):
	min_term_count = bit_count(n)
	for i in range(len(ps)):
		if ps[i] > n:
			continue
		min_term_count = min(min_term_count, 1 + solve_task(n - ps[i], ps[i + 1:]))
	return min_term_count
powers = [factorial(x) for x in range(1, 15)]
powers.reverse()
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve_task(n, [p for p in powers if p <= n]))


import itertools, sys
input = sys.stdin.readline
factorials = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200]
powers = [4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888]
for i in range(int(input())):
	num = int(input())
	minn = bin(num).count('1')
	if num in powers:
		print(1)
	else:
		list1 = []
		for i in range(1, 15):
			list1.append(list(itertools.combinations(factorials, i)))
		for i in list1:
			for j in i:
				imp = num - sum(j)
				if imp == 0:
					output = len(j)
					if output < minn:
						minn = output
				elif imp > 0:
					s = bin(imp)[2:]
					output = len(j) + s.count('1')
					if output < minn:
						minn = output
		print(minn)


import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
facs = []

def fac(n):
	if n <= 1:
		return 1
	else:
		return n * fac(n - 1)
for i in range(14):
	facs.append(fac(i + 1))

def answer(n, leftfacs):
	if n == 0:
		return 0
	default = bin(n).count('1')
	aux = [default]
	for i in range(len(leftfacs)):
		if leftfacs[i] > n:
			break
		newleftfacs = leftfacs[i + 1:]
		aux.append(answer(n - leftfacs[i], newleftfacs) + 1)
	return min(aux)
for _ in range(int(input())):
	n = int(input())
	print(answer(n, facs))


from math import *
fac = [1]
for i in range(2, 16):
	fac.append(fac[-1] * i)
mask = []
for i in range(int(pow(2, len(fac)))):
	su = 0
	lne = 0
	for j in range(len(fac)):
		if i & 1 << j:
			su += fac[j]
			lne += 1
	mask.append((su, lne))
for i in range(int(input())):
	n = int(input())
	ans = 12345679
	for (a, b) in mask:
		if n - a >= 0:
			ans = min(ans, bin(n - a)[2:].count('1') + b)
	print(ans)


def fact(n):
	p = 1
	for j in range(1, n + 1):
		p = p * j
	return p
lst2 = []
lstfac = []
for k in range(1, 16):
	lstfac.append(fact(k))

class py_solution:

	def sub_sets(self, sset):
		return self.subsetsRecur([], sorted(sset))

	def subsetsRecur(self, current, sset):
		if sset:
			return self.subsetsRecur(current, sset[1:]) + self.subsetsRecur(current + [sset[0]], sset[1:])
		return [current]
lst1 = py_solution().sub_sets(lstfac)
lst2 = []
for h in lst1:
	lst2.append((sum(h), len(h)))

def decimalToBinary(n):
	return bin(n).replace('0b', '')
t = int(input())
for i in range(t):
	n = int(input())
	lstf = []
	for f in lst2:
		dif = n - f[0]
		if dif >= 0:
			s = decimalToBinary(dif)
			c = s.count('1')
			lstf.append(c + f[1])
	print(min(lstf))


n = [0]
p = 1
for x in range(2, 16):
	n.append(p)
	p *= x
j = {}
for y in range(1, 2 ** 15):
	l = format(y, '015b')
	s = 0
	ll = 0
	for z in range(14, -1, -1):
		if l[z] == '1':
			s += n[14 - z]
			ll += 1
	j[s] = ll
a = int(input())
for x in range(a):
	b = int(input())
	t = {}
	ans = 999999999999999999
	for y in j:
		if y <= b:
			t[format(b - y, '050b')] = j[y]
	for y in t:
		ans = min(ans, y.count('1') + t[y] - 1)
	print(ans)


test = int(input())
factorial = []
subsets = [[]]
fact = 1
for i in range(1, 15):
	fact *= i
	factorial.append(fact)
for i in factorial:
	l = len(subsets)
	for j in range(l):
		k = subsets[j].copy()
		k.append(i)
		subsets.append(k)
while test:
	n = int(input())
	ans = float('inf')
	for i in subsets:
		s = sum(i)
		if s > n:
			continue
		ct = len(i)
		b = bin(n - s)
		if 1 in i and b[-1] == '1':
			continue
		elif 2 in i and b[-2] == '1':
			continue
		else:
			ct += b.count('1')
		ans = min(ans, ct)
	print(ans)
	test -= 1


import bisect
t = int(input())
a = [0 for i in range(16)]
a[0] = 1
for i in range(1, 16):
	a[i] = i * a[i - 1]
s = []
for i in range(2 ** 12):
	s.append(format(i, '#010b')[2:])
ss = []
for c in s:
	sum = 0
	times = 0
	c = c[::-1]
	for i in range(0, len(c)):
		if c[i] == '1':
			sum += a[i + 3]
			times += 1
	ss.append((sum, times))

def countSetBits(num):
	count = 0
	while num:
		count += num & 1
		num >>= 1
	return count
while t > 0:
	t -= 1
	n = int(input())
	N = n
	mn = 66
	for (x, y) in ss:
		if n >= x:
			mn = min(mn, countSetBits(n - x) + y)
	if mn == 66:
		print(-1)
	else:
		print(mn)


import math

def fun(x, lst, n):
	if x - lst[n] < 0:
		return bin(x).count('1')
	else:
		return min(fun(x - lst[n], lst, n + 1) + 1, fun(x, lst, n + 1), bin(x).count('1'))
num = []
k = []
num1 = sorted(list({math.factorial(i) for i in range(1, 16)}))
N = int(input())
for i in range(N):
	num.append(int(input()))
for i in num:
	if bin(i).count('1') == 1 or i in num1 == 1:
		k.append(1)
	else:
		k.append(fun(i, num1, 0))
for i in k:
	print(i)


import math

def comb(A):
	if len(A) == 1:
		return [[A[-1]], []]
	return [c + [A[-1]] for c in comb(A[:-1])] + comb(A[:-1])

def calc(A):
	count = 0
	while A:
		if A & 1 == 1:
			count += 1
		A = A >> 1
	return count
fact = [i for i in range(3, 15)]
combs = comb(fact)
combs = combs[::-1]
fact_sum = dict()
for (i, com) in enumerate(combs):
	summ = sum([math.factorial(c) for c in com])
	fact_sum[i] = summ

def sol(n):
	ans = 2 ** 31
	for (i, com) in enumerate(combs):
		summ = fact_sum[i]
		if n < summ:
			break
		ans = min(ans, len(com) + calc(n - summ))
	return ans if ans != 2 ** 31 else -1
x = int(input())
for _ in range(x):
	n = int(input())
	print(sol(n))


def main_tc(good_numbers):
	n = int(input())
	answer = 10000
	for good_number in good_numbers:
		if n >= good_number[0]:
			remaining = n - good_number[0]
			answer = min(answer, good_number[1] + get_bit_count(remaining))
	print(answer)

def get_bit_count(n):
	answer = 0
	while n > 0:
		answer += n & 1
		n >>= 1
	return answer

def main():
	tc = int(input())
	good_numbers = [(0, 0)]
	factorials = []
	cur = 2
	for i in range(3, 15):
		cur *= i
		factorials.append(cur)
	for f in factorials:
		extension_good_numbers = []
		for number in good_numbers:
			extension_good_numbers.append((number[0] + f, number[1] + 1))
		good_numbers.extend(extension_good_numbers)
	for _ in range(tc):
		main_tc(good_numbers)
main()


import sys

def input():
	return sys.stdin.readline().rstrip()

def solution(n: int) -> int:
	INF = 53

	def backtrack(pos, cnt, cur_sum):
		if cur_sum == n:
			return cnt
		elif cur_sum > n:
			return INF
		elif suffix_sum[pos] < n - cur_sum:
			return INF
		if pos == len(num_list):
			return INF
		return min(backtrack(pos + 1, cnt + 1, cur_sum + num_list[pos]), backtrack(pos + 1, cnt, cur_sum))
	power_nums = set()
	num = 2
	while num <= n:
		power_nums.add(num)
		num *= 2
	num = 1
	i = 2
	while num <= n:
		power_nums.add(num)
		num *= i
		i += 1
	num_list = sorted(list(power_nums))
	suffix_sum = [0]
	for num in num_list:
		suffix_sum.append(suffix_sum[-1] + num)
	suffix_sum.reverse()
	num_list.reverse()
	min_k = backtrack(0, 0, 0)
	if min_k == INF:
		return -1
	else:
		return min_k

def main():
	t = int(input())
	for tc in range(t):
		n = int(input())
		print(solution(n))
main()


from math import factorial
from sys import stdin
from itertools import combinations
list2 = []
for i in range(15):
	list2.append(factorial(i))
list1 = []
for i in range(15):
	for j in combinations(list2, i):
		list1.append([len(j), sum(j)])
tc = int(input())
for j in range(tc):
	x = int(input())
	list3 = []
	for (i, k) in list1:
		if x - k >= 0:
			a = bin(x - k)
			list3.append(i + a.count('1'))
	print(min(list3))