Tại vương quốc Checkerboard, đức vua sở hữu một quảng trường khổng lồ được lát bằng các viên gạch màu đen và trắng. Quy luật lát gạch của vương quốc rất đặc biệt:

• Quảng trường có kích thước vô tận.
• Các hàng được đánh số từ \(1, 2, 3, \dots\) từ trên xuống dưới.
• Các cột được đánh số từ \(1, 2, 3, \dots\) từ trái sang phải.
• Ô ở hàng \(1\), cột \(1\) có màu đen.
• Hai ô kề cạnh nhau (chung cạnh) luôn có màu khác nhau.

Vì quảng trường quá rộng lớn, đức vua thường xuyên đố các quan cận thần xác định màu sắc của một ô ở vị trí bất kỳ. Bạn hãy giúp các quan cận thần trả lời những câu hỏi của đức vua nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 10^5\)) — số lượng câu hỏi của đức vua.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(R\) và \(C\) (\(1 \le R, C \le 10^{12}\)) — tọa độ hàng và cột của ô cần kiểm tra.

Output

• Với mỗi câu hỏi, in ra trên một dòng: den nếu ô đó màu đen, hoặc trang nếu ô đó màu trắng.

Example

3
1 1
1 2
2 2

den
trang
den

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(T \le 100\) và \(R, C \le 15\).
• Subtask \(2\) (\(30\%\) số điểm): \(T \le 1000\) và \(R, C \le 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(T \le 10^5\) và \(R, C \le 10^{12}\).