Parenthesis Sequence Character

Interview

Time limit1sMemory limit1024 MB

Summary

Given n and k, find the k-th character of the bracket string S_n = (S_{n-2} S_{n-1}), or print 0 if k exceeds its length.

Level: Medium5 of 10
Topics: Recursion, Math, String
Solved: No attempts yet

Problem

Define the sequence $S$ of strings as follows.

$S_1 =$ ()

$S_2 =$ ()

$S_n =$ ( $S_{n-2} S_{n-1}$ ) for $n \geq 3$

Find the $k$ -th character of $S_n$ . The first character of $S_n$ has index $1$ .

Input

The first line contains the number of test cases $T$ ( $1 \leq T \leq 1\,000$ ). Each of the next $T$ lines contains integers $n$ and $k$ ( $1 \leq n, k \leq 10^{18}$ ).

Output

For each test case, print the $k$ -th character of $S_n$ . If $k$ is greater than the length of $S_n$ , print 0 instead.

Hint

By the definition above,

$S_3 =$ (()())

$S_4 =$ (()(()()))

$S_5 =$ ((()())(()(()())))

Examples1

Example 1
Input
```
3
3 7
4 7
5 7
```
Expected output
```
0
(
)
```