After the magic spell is printed, they find that they’ve already reach the Holy Candy Mountain, which is so magnificent that Little Graphy can’t even breathe. While Little Graphy is still in shock, a huge banana drops down in front of them out of the blue.
“Hey! It’s Banana King!” Pinky shouts, “What is he doing here?”
“Hummm, I think he’s dead.” Blues bounces on the body of Banana King.
“Wowwwwww, dead banana! Maybe it is time to have some fruit!” Pinky says excitedly, peeling the banana.
“Stop it, Pinky. We had better move on,” Little Graphy says with its trembling sound, “the sky is getting dark.”
They quickly bypass the dead Banana King, going straightly up to the summit. As soon as they cross one of the forests on the hillside, a woman with a black cloak appears.
“I’m Black Dark Witch. What are you guys doing here?” the woman stares at them.
“We’re here for the prone grass, do you have some?” Pinky answers, “Little Graphy is starving.”
“I think Little Graphy is hungry enough to eat a mountain of prone grass,” laughs Blues.
“Prone grass? Oh…okay, follow me.” Black Dark Witch says softly, entering the cottage behind her.
“Bang!” the door is slammed and locked.
“What are you doing, Little Graphy?” Blues asks.
“What? I’ve just entered, didn’t even touch the door yet!” Little Graphy says, confused.
“Hahahaha,” laughs the Black Dark Witch, “Why are there so many silly guys wants to steal my prone grass away just like the stupid banana?”
“Bye, poor animals,” Black Dark Witch smiles evilly, leaving through the Scary Door.
“Wait!” Little Graphy yells, “Oh chaaaka~~ the door is locked! So scary!”
“I know the way to open the Scary Door,” says Blues.
“There’re some magic plates in the room, all of them have the same size and same pattern.”
“You should pile them in a 5*L rectangle in such a way that none of the marks on plates overlap, and L is smallest.”
“Notice that you should never flip or rotate any of them.”
However, as you know, Little Graphy can’t even solve the A+B problem. It’s your show time again!
There’re several test cases, ended with EOF.
There are two integers n;m in the first line of each test case, which means there’re m plates, with a size of 5*n.
The 2nd to 6th line of each test case represents the pattern. ‘.’ means blank. ‘X’ means mark, which can’t overlap.
• There’re no more than fifteen test cases.
• 1<=m<=20
• 5
• nm<=107
For each test case, print a line containing an integer indicating the smallest length.