Cryptarithm

Problem Statement

Cryptarithm A cryptarithm is an arithmetic puzzle in which the digits of an addition have been replaced by letters. Solving one means finding a correspondence between letters and digits that makes the addition true. A single puzzle is given as three words word1 , word2 and word3 , standing for the addition word1 + word2 = word3 . An assignment of digits to letters is a valid solution when all of the following hold: Every letter is replaced by a single decimal digit, different letters are replaced by different digits , and the same letter always takes the same digit. The leading digit of a word that is more than one letter long is not 0 . A word made of a single letter is allowed to be 0 . After the replacement, the number spelled by word1 plus the number spelled by word2 equals the number spelled by word3 . You are given T independent puzzles. For each puzzle, report how many valid solutions it has. Input Format The first line contains a single integer T — the number of puzzles. Each o