A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have huge difference in quality. The company manufactures walls of square shapes only to optimize their costs. A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-qualitymaterial-materialC. To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnacestartsheating. Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.
First Line will provide the size of the original wall N. Next N lines will provide the type of material (C and D) used for each brick by the novice employee.
Size of the biggest possible C square wall which can be fitted in the final wall.
If the wall is placed with its left side at the bottom, space for a new C wall of size 2×2 can be created.This can be visualized as follows:
The melted bricks can be visualized as follows
Hence, the maximum wall size that can be replaced is 2×2. If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3×3 can be created. Post melting, this can be visualized as follows.