Economic Game "P&T"#148
Two non-negative integers and are given. Two players — Provider () and Transit () — take turns making moves, starting with . On each turn, a player must subtract from the larger of the two numbers a positive integer that is a multiple of the smaller number, such that the result remains non-negative. The player who cannot make a move loses.
The first line contains the number of test cases (1 \le N \le 10). Each of the next lines contains two integers and (A, B < 2 \cdot 10^9).
Output a single line containing a sequence of digits, each or , written consecutively without spaces. Here, and represent the winner's number (: wins, : wins).
Example 1