Em Mạnh tự xưng mình là một chuyên gia giải mã tài ba. Vì thế nên để thử thách em Mạnh, anh Kiên đã nhờ em Mạnh tìm mã \(D\) của một số.

Mã \(D\) của một số nguyên dương sẽ thu được sau khi thực hiện chuỗi thao tác sau:

• Bước 1: Tính tổng các chữ số của số đó.
• Bước 2: Kiểm tra nếu kết quả là một số có nhiều hơn hai chữ số thì ta sẽ thực hiện lại chuỗi thao tác này cho tới khi kết quả là một chữ số.

Ví dụ: \(2064 \to 2+0+6+4 = 12 \to 1 + 2 = 3\). Do vậy mã \(D(2064) = 3\).

Nhưng để thử thách hơn thì anh Kiên đưa cho em Mạnh số nguyên \(N\) và bảo em Mạnh tính mã \(D\) của \(N\) giai thừa \((D(N!))\).

Em Mạnh đang rất lo lắng vì nếu không hoàn thành được bài này, mọi người sẽ phát hiện ra rằng Mạnh chỉ BỐC PHÉT. Em Mạnh khẩn thiết nhờ mọi người giúp đỡ để xử lý bài này.

Đầu vào

Dòng đầu chứa số nguyên \(T\) là số lượng bộ test. \((1 \le T \le 100000)\)

\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\). \((0 \le N \le 10^{18})\)

Đầu ra

\(T\) dòng, mỗi dòng là kết quả mã \(D\) của \(N\) giai thừa \((D(N!))\).

Giới hạn

\(20\%\) số test: \(0 \le N \le 10\)

\(80\%\) số test: Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4
1
3
5
13

Đầu ra

1
6
3
9

Giải thích

Ở hai testcase đầu, ta thấy \(1!\) và \(3!\) đầu có kết quả là số có một chữ số là \(1\) và \(6\).

Ở testcase thứ ba, \(D(5!) = D(120) = 1 + 2 + 0 = 3\).

Ở testcase thứ tư, \(D(9!) = D(362880) = 3 + 6 + 2 + 8 + 8 + 0 = 27 \to 2 + 7 = 9\).