PTIT013K spoj PTIT – SỐ NGUYÊN HỆ CƠ SỐ ACM

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT013K/

1. Đề bài PTIT013K spoj

Số nguyên hệ cơ số ACM là những số nguyên thông thường sử dụng các ký hiệu từ 0,1,…,9 làm ký hiệu hệ đếm (ví dụ số 719_ACM). Nguyên tắc chung để đổi một số A = (aN, aN-1, …,a1) ở hệ cơ số ACM sang số ở hệ cơ số 10 được thực hiện như sau:

K₁₀ = sum a_i * i!

trong đó a_i chữ số tại vị trí thứ i của hệ cơ số ACM.

Ví dụ: A = 719_ACM = 9.(1!) + 1*(2!) + 7.(3!) = 53₁₀

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu  tiên chứa một số nguyên không lớn hơn 100 là số lượng các bộ dữ liệu.

Mỗi bộ dữ liệu viết trên một dòng một số nhỏ hơn 2^32 là các số ở hệ cơ số ACM.

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số trong hệ cơ số 10 được chuyển đổi tương ứng với dữ liệu vào.

Example

Input:
6
719
1
15
110
102
8
Output:
53
1
7
8
8
8

2. Hướng dẫn PTIT013K spoj PTIT

– Thực hiện duyệt trâu bình thường ĐPT có thể lên đến O(100*10*10)

– để tiện, ở code mẫu pascal mình tính sẳn kết quả giai thừa, giảm ĐPT xuống còn O(100*10)

Tuy nhiên ở bài này, làm ĐPT O(100*10*10) vẫn AC