CUTSQRS - Cutting off Squares


Two players take it in turns to cut off squares from a rectangle. If the lengths of the sides of the rectangle are a and b (a<=b) at the beginning of a player's turn, he may cut off as many squares with a side of length a as he likes (but at least 1 square), provided the square he is cutting off has at least three of its sides lying on the sides of the rectangle he is trimming. After every cut, the cut off square is removed from the rectangle. When the last part of the rectangle is removed, the game ends and the person who cut it off wins.

Michael, a friend of the players', is taking down a log of the games they are playing in the form of a sequence of consecutive numbers, each number denoting how many squares a player cut off in his turn. Since the game is rather slow, Michael is getting a little bored and he has started writing a detailed analysis of the game in his notebook. For given starting dimensions a and b, he always writes down:

  • the number of different possible game sequences,
  • the number of different possible game sequences in which the starting player wins,
  • the word 'first' if the starting player can win (provided he does not make any mistakes) regardless of what the other player does, and the word 'second' in all other cases.

After writing for several hours Michael began to worry whether he had enough room left in his notebook for all the information he wanted to write down. Please help him answer this question.

Input

An integer t denoting the number of test cases, (t<=10000) followed by t pairs of integers a, b, (1<=a<=b<=109) given in separate lines.

Output

For each test case, output the number of characters Michael has to write down (excluding spaces).

Example

Sample input:
2
1 1
2 3

Sample output:
7
8

(In the first case Michael has to write '1 1 first', in the second case '2 1 second'.)


hide comments
fkltcbuy: 2015-07-11 19:03:31

@Aditya: You are correct that is the only possible sequence of cuts. However, there can be two "game sequences" with that same sequence of cuts:

1) Player 1 cuts a 2x2 square -> Player 2 cuts one 1x1 square -> Player 1 cuts one 1x1 square -> Player 1 wins.

and

2) Player 1 cuts a 2x2 square -> Player 2 cuts both 1x1 squares -> Player 2 wins.

Aditya Agrawal: 2015-05-27 20:45:18

Not getting second test case . There is only one possible sequence 2,3 -> 1,2 -> 1,1

Paul Draper: 2012-12-09 00:33:50

Are the following cases correct?

2
43 100
123456789 987654321

16
8258720


Added by:adrian
Date:2004-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:DASM Programming League 2004 (problemset 1)