Петоріс
Ви граєте в головоломку під назвою petoris. Гра відбувається на дошці, поділеній на квадратні клітинки, і квадратних плитках, кожна з яких підходить для однієї клітинки. На кожному кроці гри у вас є дошка, частково заповнена плитками. У вас також є блок, що складається з кількох плиток. Ви повинні розмістити цей блок десь на дошці або відкинути його, дотримуючись наступних обмежень на розміщення:
блок можна повертати, але не можна ділити чи перевертати;
жодна з плиток блоку не може стикатися з будь-якими плитками, що вже є на дошці; та
всі плитки блоку повинні бути розміщені всередині дошки.
Ваше завдання — написати програму, яка знайде максимальний бал, який ви можете заробити на цьому кроці. Тут бал — це кількість горизонтальних рядків, повністю заповнених плитками після розміщення блоку, або −1 у разі відкидання.
Вхідні дані
Перша строка введення — це N, кількість наборів даних. Далі йдуть N наборів даних. Кожен набір даних складається з рядків, що описують блок і дошку. Кожен опис (як для блоку, так і для дошки) починається з рядка, що містить два цілі числа H і W, вертикальний і горизонтальний розмір. Потім слідують H рядків, кожен з W символами, де '#' представляє плитку, а '.' — порожнє місце. Ви можете припустити, що 0 < H ≤ 64 і 0 < W ≤ 64. Кожен блок складається з однієї або більше плиток, всі з яких з'єднані. Кожна дошка містить нуль або більше плиток і не має горизонтального рядка, повністю заповненого плитками на початковому етапі.
Вихідні дані
Для кожного набору даних виведіть в одному рядку максимальний можливий бал.