Xavier вчиться рахувати
Ксав'єр, 9-річний учень, обожнює різноманітні головоломки. Одна з його улюблених виглядає так:
Його однокласниця Ксерієр підготувала багато карток. На кожній картці вона записала одне позитивне число, причому числа на різних картках не повторюються. Потім вона складає рівняння, де права частина - це одне позитивне число, яке вона обрала, а ліва частина - це сума p цілих чисел:
Після цього вона просить Ксав'єра розмістити p карток на відповідних позиціях X_i, щоб зробити рівняння правильним, з умовою, що X_i повинні бути розташовані у порядку зростання.
Ксав'єр завжди швидко знаходить багато рішень. Тепер він хоче знати, скільки всього існує рішень для будь-якого n, заданого Ксерієр.
Вхідні дані
Є кілька тестових випадків. Їх кількість вказана на початку введення. Далі йдуть блоки введення для кожного випадку.
Для кожного тестового випадку:
У першому рядку містяться два цілі числа, розділені пробілом, m і p (1 ≤ p ≤ 5). У другому рядку містяться m різних позитивних цілих чисел - числа, записані на кожній з карток. Жодне з цих чисел не перевищує 13000.
Загалом є близько 120 тестових випадків, але 90% з них відносно невеликі. Точніше, всі числа менші або дорівнюють 100 у 90% тестових випадків.
Вихідні дані
Для кожного тестового випадку:
Для кожного позитивного цілого числа виведіть кількість способів в одному рядку. Щоб зберегти вихідні дані скінченними, слід виводити лише числа з позитивними способами.
Виведіть порожній рядок після кожного тестового випадку. Дивіться зразок для деталей формату.