ABCD 코드

바샤는 자주 페탸네 집에 놀러 간다. 페탸네 집 마당에 들어가려면 네 자리 숫자로 이루어진 코드를 입력해야 한다. 보통은 친구들이 함께 갔지만, 이번에는 바샤가 혼자 왔고 페탸는 집에서 기다리고 있다.

바샤는 코드를 기억하지 못하지만, 몇 가지 후보는 가지고 있다. 게다가 바샤는 코드의 처음 두 자리로 만든 수의 제곱과 코드의 마지막 두 자리로 만든 수의 제곱의 합을 7로 나눈 나머지가 1이라는 사실을 왠지 기억하고 있다. 즉, 코드가 <<$ABCD$>>이고 <<$A$>>, <<$B$>>, <<$C$>>, <<$D$>>가 각각 어떤 숫자라면, $AB^2 + CD^2$를 7로 나눈 나머지는 1이다. 예를 들어 코드 2843은 가능한 코드 중 하나인데, $28^2 + 43^2=2633 = 376 \cdot 7 + 1$이기 때문이다. 반면 8243은 $82^2 + 43^2=8573 = 1224 \cdot 7 + 5$이므로 아니다.

바샤는 코드가 될 수 있는 후보를 여러 개 가지고 있다. 그중 어떤 후보가 페탸네 집 마당 입구의 코드가 될 수 있는지 판별하자.

첫째 줄에 바샤가 기억하는 코드 후보의 수 $t$ ($1 \le t \le 10\,000$)가 주어진다. 다음 $t$개 줄에 각각 네 자리 숫자로 이루어진 코드 후보가 하나씩 주어진다.

$t$개 줄을 출력한다. $i$번째 줄에는 $i$번째 코드가 페탸네 집 마당 입구의 코드가 될 수 있으면 <<YES>>, 아니면 <<NO>>를 출력한다.