By Alexandre Campos, UNIUBE Brazil
In Brazil, the equivalent to Social Security Number is usually called CPF. It is composed by 11 digits and the two lasts are function of the nine previous. In this way, if a person informs a CPF, by mistake or on purpose, it is possible to find out. Let us introduce some notation. Let a CPF be
To get b1, one can multiply a1 by 1, a2 by 2, a3 by 3, so on, up to a9 by 9 and sum these results. Then, b1 is the remaining of this number when divided by 11, or 0 in case the remaining is 10.
Analogous, to get b2, one can multiply a1 by 9, a2 by 8, a3 by 7, so on, up to a9 by 1 and sum these results. Then, b2 is the remaining of this number when divided by 11, or 0 in case the remaining is 10.
Given a CPF number, you have to tell whether it is valid or not.
The input is composed by an unknown number of CPF numbers, not more than 10000 cases. Each line has a CPF in the form
If the given CPF is valid, print "CPF valido". Otherwise, print "CPF invalido".
|Input Sample||Output Sample|