괄호 수열의 k번째 문자

면접 대비

시간 제한1초메모리 제한1024 MB

요약

주어진 n과 k에 대해 S_n = (S_{n-2}S_{n-1}) 로 정의된 괄호 문자열의 k번째 문자를 구합니다. k가 길이를 넘으면 0을 출력합니다.

문제

다음과 같이 문자열의 수열 $S$ 를 정의한다.

$S_1 =$ ()

$S_2 =$ ()

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

$S_n$ 의 $k$ 번째 문자를 구하여라. 단, $S_n$ 의 맨 처음 문자의 인덱스는 $1$ 이다.

첫 번째 줄에 테스트 케이스의 수 $T$ 가 주어진다. ( $1 \leq T \leq 1\,000$ ) 두 번째 줄부터 $T$ 개의 줄에 정수 $n$ , $k$ 가 주어진다. ( $1 \leq n, k \leq 10^{18}$ )

각 테스트 케이스마다 $S_n$ 의 $k$ 번째 문자를 출력한다. $k$ 가 $S_n$ 의 길이보다 크면 대신 0을 출력한다.

위의 정의에 따라,

$S_3 =$ (()())

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

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