Digit Factorial Sum

Given a positive integer n, compute the sum of the factorials of its digits. For a given number n with digits \(d_1, d_2, \dots, d_k\), the answer is given by:

[ S = \sum_{i=1}^{k} d_i! ]

Note: Since the value of n can be very large, it is recommended to process the number as a string.

inputFormat

The first line contains an integer T indicating the number of test cases. Each of the following T lines contains a single positive integer n.

outputFormat

For each test case, output a single line containing the sum of the factorials of the digits of n.

sample

1
145

145