Chess Practice

Sejun and Dasom enjoy playing chess as a hobby. Now they are training with the goal of joining the national team. Today they practice attacking techniques using only queens on a 100 by 100 chessboard.

There are N queens on the board. Sejun moves first, then Dasom, and they continue alternating turns.

On one turn, the player chooses one queen and moves it. If the queen is at (x, y), the player may choose a positive integer k and move it to one of (x-k, y), (x, y-k), or (x-k, y-k). A queen may pass through squares occupied by other queens, and multiple queens may occupy the same square.

The first player to place any queen on (0, 0) wins. Assuming both players play optimally, determine the winner of each game.

The input contains 5 games. Each game has the following format.

The first line contains N, the number of queens on the board. N is at most 50. Each of the next N lines contains a queen position X Y. No queen is initially at (0, 0).

For each game, print S if Sejun wins, or D if Dasom wins, one result per line.