SP660 QUEST4 - Dungeon of Death

To reach the treasure, **Jones** has to pass through the **"Room of Death"**. The floor of this room is a square with side **120** units. It is laid with square tiles of dimensions **{1 X 1}** arranged into a grid. But, at some places in the grid tiles are missing. As soon as the door to this room is opened poisonous gas starts coming out of these missing grid locations. The only escape from this gas is to completely cover these locations with planks lying outside the room. Each plank has dimensions **{120 X 1}** and can only be placed parallel to either sides of the floor. Now **Jones** wants to minimize the damage to his health so that he has enough of it left for the treasure. He figures out that in order to achieve this he has to use the minimum number of planks possible. He also realises that even if the planks overlap, poisonous gas from the missing tiles can still be successfully blocked. Please help **Jones** in this task. 

- The first line of the input is a positive integer **t

The output should consist of **t** lines, one for each room. The **k $ ^{th} $** line in the output should be an integer **m $ _{k} $** , the minimum number of planks needed for the **k $ ^{th} $** room.