Someone put a physical mirror in the holodeck chamber, and it has scrambled some critical simulation data! The mirror had the eect of superimposing reversed data on top of the original data. You need to gure out how scrambled the data is. Given a positive number \textbf{Y}, calculate the number of distinct positive values of \textbf{X} such that \textbf{Y = X + rev(X)}. The \textbf{rev }operator reverses the digits of a number. The values for \textbf{X} must be in their normal decimal form, without leading zeros. For example, \textbf{rev(350) = 53} and \textbf{rev(53) = 35}. \InputFile Input begins with a line with one integer \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{500}) denoting the number of test cases. Each test case consists of a single line with a single integer \textbf{Y} (\textbf{1} ≤ \textbf{Y} < \textbf{10^18}). \OutputFile For each test case, print out a line containing the count of positive integers that, when summed with their reverse, equals the input value.