Company: Silvermine
Difficulty: medium
Magical Numbers In a realm of enchantment, magical numbers possess a unique property. A magical number can be defined as a number that has a special quality – it can be represented either as a power of two or as the result of a factorial. To be deemed magical, a non-negative integer d must meet one of these conditions: it must either equal 2 a or a! , where d represents the product of all positive integers from 1 to a (remarkably, 0! is set as 1 ). For example, numbers like 1 , 4 , and 6 are classified as magical numbers because they satisfy the conditions: 1=1! , 4=2^2 , and 6=3! . However, numbers such as 7 , 10 , or 18 do not share this enchanting property. Given a positive integer n , your task is to discover the smallest k where n can be constructed as the sum of k distinct magical numbers. If it proves to be impossible to represent n in this manner, kindly indicate this in your response. Input Format Each test contains multiple test cases. The first line contains the number of te