Dãy số \(Fibonacii\) được định nghĩa như sau:

\(F_1=1;F_2=1;F_i=F_{i-1}+F_{i-2} (i≥3).\)

Dãy các số \(Fibonacii\) đầu tiên: \(1, 1, 2, 3, 5, 8, 13, …\)

Yêu cầu: Cho số nguyên dương \(N\). Tính tích các chữ số của \(N\) số \(Fibonacii\) đầu tiên.

Dữ liệu Vào từ file văn bản FIBP.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(t(1≤t≤10^5)\)

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N(1≤N≤10^9).\)

Kết quả ghi vào file văn bản FIBP.OUT có cấu trúc:

• Ghi \(t\) dòng, mỗi dòng ghi một số nguyên là kết quả tìm được của test tương ứng khi chia lấy dư cho \(1234567891.\)

Ràng buộc

• Subtask 1: \(N≤10^6\)

• Subtask 2:\( N≤10^9\)

Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
6
30