SumOfPowers#2687
Bəzi natural ədədlər, məsələn, 9 = 3^2, natural ədədlərin mükəmməl kvadratlarıdır. Digərləri, məsələn, 17 = 4^2 + 1^2, iki kvadratın cəmi şəkildə ifadə oluna bilər. Bəziləri isə, məsələn, 6 = 2^2 + 1^2 + 1^2, ən azı üç kvadrata ehtiyac duyur və sair. Bu cür hesablamaları təkcə kvadratlar üçün yox, digər dərəcələr üçün də aparmaq olar. Məsələn, natural ədədin kubu deyil və iki kubun cəmi kimi ifadə oluna bilməz, lakin üç kubun cəmi şəklində ifadə oluna bilər: 2^3 + 2^3 + 1^3. Hər bir N_1, N_2, \ldots, N_M ədədinin cəmi kimi ifadə olunması üçün ən az neçə natural ədədin -ci qüvvətinin lazım olduğunu tapacaq proqram yazın.
İlk olaraq qüvvət (1 \leq K \leq 98), sonra isə hesablama aparılmalı olan ədədlərin sayı (1 \leq M \leq 9876) verilir. Daha sonra ədədlərin özü verilir: N_1, N_2, \ldots, N_M (hər biri 1 \leq N_i \leq 987654). Bütün dəyərlər bir sətirdə, aralarında bir boşluq olmaqla verilir.
Bir sətirdə ədəd yazın; hər biri uyğun olaraq N_1, N_2, \ldots, N_M ədədlərini ifadə etmək üçün lazım olan ən az -ci qüvvətlərin sayıdır. Ədədlər arasında bir boşluq qoyun.
Nümunə 1