23952번 - Elevanagram 서브태스크다국어

문제

It is a well known fact that a number is divisible by 11 if and only if the alternating sum of its digits is equal to 0 modulo 11. For example, 8174958 is a multiple of 11, since 8 -ひく 1 +たす 7 -ひく 4 +たす 9 -ひく 5 +たす 8 =わ 22.

Given a number that consists of digits from 1-9, can you rearrange the digits to create a number that is divisible by 11?

Since the number might be quite large, you are given integers A₁, A₂, ..., A₉. There are A_i digits i in the number, for all i.

입력

The first line of the input gives the number of test cases, T. T lines follow. Each line contains the nine integers A₁, A₂, ..., A₉.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is YES if the digits can be rearranged to create a multiple of 11, and NO otherwise.

제한

• 1 ≤ T ≤ 100.
• 1 ≤ A₁ + A₂ + ... + A₉.

Test Set 1 (20점)

• 0 ≤ A_i ≤ 20, for all i.

Test Set 2 (27점)

• 0 ≤ A_i ≤ 10⁹, for all i.

힌트

• In Sample Case #1, the digits are 336, which can be rearranged to 363. This is a multiple of 11 since 3 - 6 + 3 = 0.
• In Sample Case #2, the digits are 999999999999, which is already a multiple of 11, since 9 - 9 + 9 - 9 + ... - 9 = 0.
• In Sample Case #3, the digits are 5578, which cannot be rearranged to form a multiple of 11.
• In Sample Case #4, the digits are 111234, which can be rearranged to 142131. This is a multiple of 11 since 1 -ひく 4 +たす 2 -ひく 1 +たす 3 -ひく 1 =わ 0.
• In Sample Case #5, the digits are 11177799, which can be rearranged to 19191777. This is a multiple of 11 since 1 -ひく 9 +たす 1 -ひく 9 +たす 1 -ひく 7 +たす 7 -ひく 7 =わ -ひく22 (which is 0 modulo 11).
• In Sample Case #6, the only digit is 8, which cannot be rearranged to form a multiple of 11.