파스칼과 불

많은 사람이 파스칼 삼각형을 알고 있다. 파스칼 삼각형은 정수를 삼각형 모양으로 배열한 것으로, 프랑스의 수학자이자 철학자인 블레즈 파스칼(1623-1662)의 이름을 따서 불린다. 위에서부터 행에 $1, 2, 3, \ldots,$ 번호를 붙이면, $r$행에는 $r$개의 원소가 있고, 왼쪽에서 오른쪽으로 $1, 2, \ldots, r$번 번호를 붙인다. $r$행의 1번째 원소와 $r$번째 원소는 모두 $1$이다. $r \geq 3$이고 $1 < i < r$이면, $r$행의 $i$번째 원소는 $r-1$행의 $i-1$번째 원소와 $i$번째 원소의 합이다. 쉽게 말해, 가장자리가 아닌 원소는 바로 위에 있는 두 원소의 합이다. 그림 J.1(a)는 파스칼 삼각형의 처음 $8$행을 보여 준다.

그림 J.1: (a) 파스칼 삼각형, (b) 함수 $1000$으로 만든 파스칼-불 삼각형

값을 합치는 규칙으로 일반적인 덧셈 말고 다른 것을 쓰면 어떻게 될까? 가장자리 원소는 비트(1)이므로, 자연스러운 선택은 임의의 두 입력 불 함수를 쓰는 것이다. 이 이름은 영국의 수학자이자 철학자인 조지 불(1815-1864)에게서 왔다. 예를 들어, 아래 진리표로 주어진 불 함수는 그림 J.1(b)의 삼각형을 만든다(처음 $8$행도 함께 보여 준다). 이 진리표에서 $x$와 $y$는 각각 $r-1$행의 $i-1$번째 원소와 $i$번째 원소에 대응하고, $f(x,y)$는 $r$행의 $i$번째 원소가 된다.

일반적으로 이런 진리표의 가장 오른쪽 열에 있는 비트를 위에서 아래로 $b_{00}, b_{01}, b_{10}, b_{11}$이라고 하면, 두 입력 불 함수는 4비트 문자열 $b_{00} b_{01} b_{10} b_{11}$로 간결하게 나타낼 수 있다. 위 예시 함수는 1000으로 나타낸다.

파스칼-불 삼각형에 대해 다음 두 종류의 질문에 답하는 것이 과제다.

1. 주어진 불 함수 $f$에서, 행 $r$, 위치 $i$의 비트는 무엇인가?
2. 주어진 불 함수 $f$에서, 처음 $r$행에 1이 몇 개 있는가?

입력의 첫 줄에는 테스트 케이스의 수 $n$ $(1 \leq n \leq 250)$이 주어진다. 이어서 $n$개의 줄이 주어지며, 각 줄은 다음 두 형식 중 하나이다.

• $f$ B $r$ $i$
• $f$ N $r$

두 경우 모두 $f$는 두 입력 불 함수를 나타내는 4비트 이진 문자열이고, $r$은 정수 $(1 \leq r \leq 10^6)$이다. 첫 번째 형식에서 $i$는 정수 $(1 \leq i \leq r)$이다.

$f$ B $r$ $i$ 형식의 테스트 케이스에 대해, $f$로 생성한 파스칼-불 삼각형의 행 $r$, 위치 $i$에 있는 비트를 한 줄에 출력한다. $f$ N $r$ 형식의 테스트 케이스에 대해, $f$로 생성한 파스칼-불 삼각형의 처음 $r$행에 있는 1의 개수를 한 줄에 출력한다.