Tính SoDo một số nguyên dương sẽ được thể hiện bởi chuỗi công việ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 công việc này cho tới khi kết quả là 1 chữ số.

Ví dụ: 901 → 9 + 0 + 1 = 10 → 1 + 0 = 1. Do vậy SoDo(901) = 1. Bạn được cho một số nguyên dương N, bạn hãy tính SoDo của N giai thừa (SoDo(N!)).

Đầu vào

• Dòng đầu tiên là chữ số nguyên t(1 <= t <= 10^5) - Tương ứng với số lượng test.
• T dòng tiếp theo mỗi dòng sẽ chứa một số nguyên N (0 ≤ N ≤ 10^18).

Đầu ra

• Kết quả SoDo của N giai thừa.

Ví dụ:

Đầu vào

4
1
3
5
13

Đầu ra

1
6
3
9

Giải thích:

• Ở 2 ví dụ đầu, ta có thể thấy kết quả của 1! và 3! đều đã là số có một chữ số: 1; 6.

• Ở ví dụ thứ ba, SoDo(5!) = 1 + 2 + 0 = 3.