Elevanagram

어떤 수가 11로 나누어떨어질 때, 그리고 그럴 때에만 그 수의 각 자릿수를 번갈아 더하고 뺀 합이 11로 나눈 나머지에 대해 0과 같다는 것은 잘 알려진 사실이다. 예를 들어, 8174958은 11의 배수이다. 왜냐하면 8 - 1 + 7 - 4 + 9 - 5 + 8 = 22이기 때문이다.

1-9의 숫자들로 이루어진 수가 주어질 때, 그 숫자들을 재배열하여 11로 나누어떨어지는 수를 만들 수 있는가?

그 수는 매우 클 수도 있으므로, 정수 $A_{1}$, $A_{2}$, ..., $A_{9}$이 주어진다. 모든 i에 대해, 그 수에는 숫자 i가 $A_{i}$개 있다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $A_{1}$ + $A_{2}$ + ... + $A_{9}$.

테스트 세트 1 (공개)

모든 i에 대해, 0 ≤ $A_{i}$ ≤ 20.

테스트 세트 2 (비공개)

모든 i에 대해, 0 ≤ $A_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 아홉 개의 정수 $A_{1}$, $A_{2}$, ..., $A_{9}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), 숫자들을 재배열하여 11의 배수를 만들 수 있다면 y은 YES이며, 그렇지 않으면 NO이다.

• 예제 케이스 #1에서 숫자들은 336이며, 이를 363로 재배열할 수 있다. 3 - 6 + 3 = 0이므로 이는 11의 배수이다.

• 예제 케이스 #2에서 숫자들은 999999999999이며, 9 - 9 + 9 - 9 + ... - 9 = 0이므로 이미 11의 배수이다.

• 예제 케이스 #3에서 숫자들은 5578이며, 이를 재배열하여 11의 배수를 만들 수 없다.

• 예제 케이스 #4에서 숫자들은 111234이며, 이를 142131로 재배열할 수 있다. 1 - 4 + 2 - 1 + 3 - 1 = 0이므로 이는 11의 배수이다.

• 예제 케이스 #5에서 숫자들은 11177799이며, 이를 19191777로 재배열할 수 있다. 1 - 9 + 1 - 9 + 1 - 7 + 7 - 7 = -22이고(이는 11로 나눈 나머지에 대해 0이다), 따라서 이는 11의 배수이다.

• 예제 케이스 #6에서 유일한 숫자는 8이며, 이를 재배열하여 11의 배수를 만들 수 없다.