Продаж землі
Як ви, можливо, знаєте, країна Абсурдистан сповнена аномалій. Наприклад, всю країну можна розділити на одиничні квадрати, які є або травою, або болотом. Також країна відома своїми нездатними бюрократами. Якщо ви хочете купити шматок землі (який називається ділянкою), ви можете купити лише прямокутну ділянку, тому що вони не можуть впоратися з іншими формами. Ціна ділянки визначається ними і пропорційна периметру ділянки, оскільки бюрократи не вміють множити цілі числа і, таким чином, не можуть обчислити площу ділянки.
Пер володіє ділянкою в Абсурдистані, оточеною болотом, і хоче її продати, можливо, частинами, деяким покупцям. Коли він продає прямокутну частину своєї землі, він зобов'язаний повідомити про це місцевим бюрократам. Спочатку вони скажуть йому ціну, за яку він повинен її продати. Потім вони запишуть ім'я нового власника і координати південно-східного кута ділянки, що продається. Якщо хтось інший вже володіє ділянкою з південно-східним кутом на тому ж місці, бюрократи відмовлять у зміні власника.
Пер розуміє, що може легко обдурити систему. Він може продавати ділянки, що перекриваються, тому що бюрократи перевіряють лише, чи однакові південно-східні кути. Однак ніхто не хоче купувати ділянку, що містить болото.
У цьому прикладі темні квадрати представляють болото. Пер може, наприклад, продати три перекриваючі сірі ділянки розмірами 2 × 1, 2 × 4 і 4 × 1 відповідно. Загальний периметр становить 6 + 12 + 10 = 28.
Зверніть увагу, що він може отримати більше грошей, продаючи ще більше землі. Ця фігура відповідає випадку у вхідних даних зразка.
Тепер Пер хотів би знати, скільки ділянок кожного периметра йому потрібно продати, щоб максимізувати свій прибуток. Чи можете ви йому допомогти? Ви можете припустити, що він завжди може знайти покупця для кожного шматка землі, якщо він не містить боліт. Також Пер впевнений, що жоден квадрат на його ділянці не належить комусь іншому.
Вхідні дані
На першому рядку позитивне ціле число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:
Один рядок з двома цілими числами n і m (1 ≤ n, m ≤ 1 000): розміри ділянки Пера.
n рядків, кожен з m символами. Кожен символ є або '#', або '.'. j-й символ на i-му рядку є '#', якщо позиція (i, j) є болотом, і '.', якщо це трава. Північно-західний кут ділянки Пера має координати (1, 1), а південно-східний кут має координати (n, m).
Вихідні дані
Для кожного тестового випадку:
Нуль або більше рядків, що містять повний список того, скільки ділянок кожного периметра Перу потрібно продати, щоб максимізувати свій прибуток. Більш конкретно, якщо Пер повинен продати pi ділянок з периметром i в оптимальному рішенні, виведіть один рядок "p_i × i". Рядки повинні бути відсортовані в порядку зростання i. Жодні два рядки не повинні мати однакове значення i, і ви не повинні виводити рядки з p_i = 0.