문제

바샤는 종종 페트야에게 놀러 갑니다. 페트야의 정원에 놀러 가기 위해서는 네 자리 수의 암호를 입력해야 합니다. 보통은 친구와 같이 놀러 갔지만 이번에는 바샤 혼자 놀러 왔고, 페트야는 집에서 바샤를 기다리고 있습니다.

바샤는 암호가 기억나지 않지만 몇 개의 후보는 있습니다. 또 왠지 모르겠지만, 바샤는 암호의 첫 두 자리를 이루는 숫자의 제곱과 끝 두 자리를 이루는 숫자의 제곱을 더한 값을 7로 나누었을 때 나머지가 1이라는 사실을 기억해냈습니다. 다시 말해, 암호가 <<ABCD>>이고 <<A>>, <<B>>, <<C>>, <<D>>가 각 자리를 나타낼 때, AB ^ 2 + CD ^ 2은 7로 나눴을 때 1의 나머지를 갖습니다. 예를 들어 2843은 28 ^ 2 + 43 ^ 2 = 2633 = 363 * 7 + 1이므로 가능한 암호이지만, 8243은 82 ^ 2 + 43 ^ 2 = 8573 = 1224 * 7 + 5로 불가능합니다.

바샤는 암호가 될 수 있는 몇 가지 후보를 알고 있습니다. 이 중 어떤 수가 페트야의 정원 입구의 암호인지 찾을 수 있도록 그를 도와줍시다.

입력

첫 줄의 바샤가 기억하는 암호 후보의 수 t(1 <= t <= 10000)가 주어집니다. 다음 t개의 줄에 암호 후보를 나타내는 네 자리 수가 주어집니다.

출력

t개의 줄을 출력합니다. i번째 암호가 페트야의 정원 입구의 암호가 될 수 있다면 <<YES>>를, 그렇지 않다면 <<NO>>를 i번째 줄에 출력합니다.