Στη μακρινή χώρα Αριθμανδαλουσία, η εφορία αντιστοιχεί έναν ΑΦΜ (Αριθμό Φορολογικού Μητρώου) σε κάθε κάτοικο. Ο ΑΦΜ είναι δωδεκαψήφιος. Αν τα ψηφία του ΑΦΜ είναι (από δεξιά προς αριστερά) a0 ως a11, τοτε ο ΑΦΜ είναι έγκυρος μόνο όταν:
a2*2^1+a3*2^2+a4*2^3+...+a11*2^10 = a0 + a1*10 (mod 97)
Με άλλα λόγια, τα τελευταία δύο ψηφία είναι το υπόλοιπο της διαίρεσης του πρώτου σκέλους της παραπάνω εξίσωσης, με το 97 (a1a0 <= 97).

Θέλουμε να φτιάξουμε ένα πρόγραμμα το οποίο βρίσκει λάθη στη συμπλήρωση του ΑΦΜ, στις φορολογικές δηλώσεις των Αριθμανδαλουσιανών. Θεωρούμε ότι το μόνο λάθος που μπορεί να έκανε κάποιος είναι να αναγράψει λάθος ένα ψηφίο (όχι μεταθέσεις ψηφίων ή λάθος αναγραφή περισσότερων ψηφίων ή αναγραφή λιγότερων ή περισσότερων ψηφίων ή λάθος σε περισσότερα ψηφία). Οι ΑΦΜ που έχουμε είναι πάντα 12ψήφιοι, έστω και με 0 αρχικά.

Είσοδος: Σε κάθε γραμμή της εισόδου θα δίνεται ένας υποψήφιος ΑΦΜ με 12 ψηφία.

Έξοδος: Αντίστοιχα για κάθε γραμμή της εισόδου, θα τυπώνεται σε μια γραμμή "VALID" χωρίς εισαγωγικά, αν ο ΑΦΜ είναι έγκυρος. Αν ο ΑΦΜ είναι άκυρος, θα τυπώνεται η λέξη INVALID και θα ακουλουθείται από μια σειρά όλων των πιθανών ΑΦΜ που ήθελε να δώσει ο φορολογούμενος. Η σειρά των πιθανών ΑΦΜ πρέπει να είναι ταξινομημένη αριθμητικά. Η λέξη INVALID και οι πιθανοί ΑΦΜ πρέπει να χωρίζονται μεταξύ τους με ένα μόνο κενό. Δεν πρέπει να υπάρχουν κενά στην αρχή ή το τέλος της γραμμής.

673647352210
271472111154

VALID
INVALID 271472111155 271472711154 271475111154