Problem Background

Guinness Record: A piece of paper (if a 4-kilometer toilet paper can be considered as a single sheet) can be folded a maximum of 13 times. Little X bragged about breaking this record, but he exaggerated too much.

Problem Description

Little X applied for this record with the Guinness World Records organization, but he is currently under home quarantine and cannot prove it. He has to allow them to ask him $t$ questions to confirm that he indeed broke the record.

For each question, they can ask Little X to fold a piece of paper according to a given $01$ string $s$ for $n$ times and then unfold it. For the $i$-th fold, if $s_i=0$, the paper is folded from left to right, aligning the left side with the right side; if $s_i=1$, the paper is folded from right to left, aligning the right side with the left side. All folds are made from the top. The paper will then be unfolded, returning to its original position but retaining the creases. Check if you can achieve this.

They want to know if the $k$-th crease from the left is a mountain fold (an upward protruding crease) or a valley fold (a downward凹陷ing crease). If the answer to the query is a mountain fold, output Up; otherwise, output Down. Please help the poor Little X.

Mountain fold and valley fold illustrations can be found in the sample explanation.

Input Format

This problem uses multiple test cases.

The first line contains a single positive integer $t$, representing the number of test cases.

The next $2t$ lines, with every two lines forming a group of data. For each group, the first line contains two positive integers $n$ and $k$. The next line contains a $01$ string of length $n$, representing $s$.

Output Format

$t$ lines, each containing a string representing the answer for that group of data.

Sample Input and Output

Input Sample #1

7
3 1
010
3 2
010
3 3
010
3 4
010
3 5
010
3 6
010
3 7
010

Output Sample #1

Down
Up
Up
Down
Down
Down
Up

Input Sample #2

7
3 1
011
3 2
011
3 3
011
3 4
011
3 5
011
3 6
011
3 7
011

Output Sample #2

Down
Up
Up
Down
Down
Down
Up

Input Sample #3

2
13 114
1101101111010
13 514
1101101111010

Output Sample #3

Up
Up

Notes

Sample Explanation

Sample #1 Explanation:

Dynamic address: here. Not sure why it doesn't display on Luogu.

Due to technical reasons, the GIF has slightly lower frame rates.

For Sample #2, please simulate manually.

Data Range

This problem uses bundled testing.

• Subtask 1 ($20$ pts): $t=10$, $1 \le n \le 5$;
• Subtask 2 ($80$ pts): $t=10^5$.

For $100\%$ of the data, $1 \le t \le 10^5$, $1 \le n \le 60$, $1 \le k < 2^n$.

见题面 Input 部分

见题面 Output 部分