직육면체

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

요약

직육면체의 세 변 A, B, C와 소수 p가 주어질 때, 1 x p x p 직육면체를 방향을 자유롭게 두어 빈틈없이 채울 수 있는지 판별한다.

문제

$A \times B \times C$ 모양의 직육면체를 $1 \times p \times p$ 모양의 직육면체로 채울 수 있는지 판별하시오. 단, $p$ 는 소수이다.

직육면체의 방향은 중요하지 않다. 즉, 직육면체를 돌려서 $p \times 1 \times p$ , $p \times p \times 1$ 로 채우는 것도 가능하다.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

이후 한 줄에 하나씩 테스트 케이스에 대한 정보가 주어진다. 각 테스트 케이스는 $A$ , $B$ , $C$ , $p$ 가 띄어쓰기를 사이에 두고 주어진다.

각각의 테스트 케이스에 대해 직육면체를 채울 수 있으면 1, 없으면 0을 출력한다. 한 줄에 하나씩 출력한다.