34517번 - 프랙탈과 점

문제

$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$는 소수점 셋째 자리까지 표시된 실수이다.

힌트