Casting Out Nines

You may have heard of the great mathematician Leonardo Fibonacci of Pisa (1170–1240). Among the many algorithms described in his book Liber Abaci (first published in 1202), Fibonacci described the "casting out nines" procedure for checking addition, subtraction, and multiplication. Historians say the procedure reached Europe through Arab scholars, but it was probably developed on the Indian subcontinent, so it is sometimes also called "the Hindu check".

Casting out nines is an elementary check of an arithmetic operation that relies on the congruence $10 \equiv 1 \pmod 9$. Recall that writing $x \equiv y \pmod z$ means that $x \bmod z$ equals $y \bmod z$.

Let $a$ and $b$ be natural numbers whose product is $c$, and let $\bar a$, $\bar b$, and $\bar c$ be the sums of the digits of $a$, $b$, and $c$. Then $a \equiv \bar a \pmod 9$, $b \equiv \bar b \pmod 9$, and $c \equiv \bar c \pmod 9$. Moreover $a \times b \equiv \bar a \times \bar b \pmod 9$, so $\bar a \times \bar b \equiv \bar c \pmod 9$. Therefore, if $c$ and $\bar a \times \bar b$ are incongruent modulo $9$, the multiplication must have been done incorrectly.

For example, $12345 \times 67890 = 838102050$. The digit sums of $12345$ and $67890$ are $15$ and $30$, and their product is $450$. The digit sum of $838102050$ is $27$. Since $450 \equiv 27 \equiv 0 \pmod 9$, the check agrees.

As another example, suppose someone incorrectly computes $13579 \times 24680 = 334129720$. Here $\bar a \times \bar b = 25 \times 20 = 500 \equiv 5 \pmod 9$, whereas $\bar c = 31 \equiv 4 \pmod 9$, so the multiplication is definitely wrong.

The same check applies to addition, since $a + b \equiv \bar a + \bar b \pmod 9$.

Write a program that decides whether a given addition or multiplication passes the Hindu check.

Your program is tested on one or more test cases, each given on its own input line of the form

a+b=c.

or

a*b=c.

Note the . at the end of each line. Here $a$, $b$, and $c$ are natural numbers. There are no spaces between the numbers and the symbols (+, *, =, and .), but trailing whitespace may appear after the ..

The last line of the input is a single . and is not part of the test cases.

For each test case, print one line in the format

k. result

where $k$ is the test case number (starting from $1$) and result is PASS if the addition or multiplication passes the Hindu check, and NOT! otherwise.