#216736. [GKS 2019 #H] Elevanagram

It is a well known fact that a number is divisible by if and only if the alternating sum of its digits is equal to modulo . For example, is a multiple of , since .

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

Since the number might be quite large, you are given integers . There are digits i in the number, for all i.

The first line of the input gives the number of test cases, . lines follow. Each line contains the nine integers .

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

样例输入 1

6
0 0 2 0 0 1 0 0 0
0 0 0 0 0 0 0 0 12
0 0 0 0 2 0 1 1 0
3 1 1 1 0 0 0 0 0
3 0 0 0 0 0 3 0 2
0 0 0 0 0 0 0 1 0

样例输出 1

Case #1: YES
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: YES
Case #6: NO

• In Sample Case #1, the digits are , which can be rearranged to . This is a multiple of since .
• In Sample Case #2, the digits are , which is already a multiple of , since .
• In Sample Case #3, the digits are , which cannot be rearranged to form a multiple of .
• In Sample Case #4, the digits are , which can be rearranged to . This is a multiple of since .
• In Sample Case #5, the digits are , which can be rearranged to . This is a multiple of since (which is modulo ).
• In Sample Case #6, the only digit is , which cannot be rearranged to form a multiple of .

Limits

.

.

Test set 1 (Visible)

, for all i.

Test set 2 (Hidden)

, for all i.