1629 - Goddess
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 166
Solved: 55
- Description
- Because of the ugly wall near the east ninth building, Hung don't want to self study anymore. Then he back to his dormitory.
In the dormitory, His roommate named Gaofushuai is playing mobile phone games with Lily, Gaofuhushuai's girlfriend. After a while, Gaofushuai is asked by next door to play Dota,
and leaving his girlfriend lonely.
It is really a golden chance for Hung. Hung fell in love with Lily when he met Lily in the first time.
But he knows that he doesn't have lots of money. It is impossible for him to imitate Gaofushuai to buy precious gifts for Lily. Of course, he has confidence in one thing-his intelligence.
As a result, Hung decides to invent a difficult game and show it to the Lily.
The game is played on a chessboard. The chessboard was divided to n*m blocks. Each block has a chess pieces on it initially.
The task is to remove some chess pieces so there are no 5 continuous chess pieces in any line (including horizontal, vertical and diagonal).
Less chess pieces removed, more grades players can get.
Though Hung invented it, he is so nervous that he forgot the fewest movements to solve it. Could you tell him? If you succeed, Hung will bg you at Dongyuan for thanks! - Input
- The first line contains a single integer T (T <= 100), the number of test cases.For each case, there are two integers n(5<=n <= 100) and m(5<=m<=100),
which describe the size of chessboard. - Output
- For each case, you should print one line with a integer , representing the minimal movements.
- sample input
-
1 5 5
- sample output
-
5
- hint
- source