프랙탈과 점

$n$단계 시에르핀스키 카펫의 정의는 다음과 같다.

• $0$단계: 빈 공간이 없는 정사각형이다.
• $1$단계: $0$단계 카펫을 가로와 세로로 각각 $3$등분하여 $9$개의 합동인 작은 정사각형으로 나눈다. 그중 가운데 정사각형을 지우고, 나머지 $8$개를 남긴다.
• $n$단계 $(n \ge 2)$: 이전 단계 카펫을 이루는 모든 정사각형에 대해 위와 동일한 과정을 진행한다. 즉, $n-1$단계 카펫을 이루는 모든 정사각형을 가로, 세로로 $3$등분하고 가운데 정사각형을 지운다.

$2$차원 평면 위에 주어지는 $L$단계 시에르핀스키 카펫은 다음 조건을 만족한다.

• 왼쪽 아래 꼭짓점의 좌표는 $(a, b)$이다.
• 가장 바깥 한 변의 길이는 $3^k$이다.
• 카펫의 변은 $x$축과 $y$축에 평행하다.

점 $(p, q)$가 주어진 시에르핀스키 카펫 위에 있는지 구해보자. 점이 카펫의 채워진 영역 안 또는 그 경계선 위에 있으면 카펫 위에 있다고 간주한다.

총 $T$개의 테스트 케이스가 입력으로 주어지며, 첫 번째 줄에 $T$가 주어진다.

그다음 줄부터 각 테스트 케이스마다 하나의 줄에 $a$, $b$, $L$, $k$, $p$, $q$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 주어진 순서대로 한 개의 줄에 점이 카펫 위에 있다면 1을, 없다면 0을 출력한다.

• $1 \le T \le 33333$
• $0 \le L \le k \le 33$
• $-3^{33} \le a, b, p, q \le 3^{33}$
• $a$, $b$는 정수이다.
• $p$, $q$는 소수점 셋째 자리까지 표시된 실수이다.