Hôm nay những chú ngựa ở quận Nottingham được học Tin học, lãnh đạo quận đã cho mời thầy Dũng (người có điểm SAT rất cao) đến dạy cho các chú ngựa.

Những chú ngựa ở trường đua Nottingham cũng không phải dạng vừa (biết cài Giải thuật tìm kiếm mô phỏng luyện kim), nên thầy Dũng đã ra một câu hỏi như sau: Cho số nguyên dương N, hãy tìm số nguyên M nhỏ nhất sao cho M! có đúng N chữ số 0 ở cuối.

Input

• Dòng đầu tiên: chứa số nguyên T (~ 1 ≤ T ≤ 10^5 ~).

• T dòng tiếp theo: mỗi dòng chứa một số nguyên N (~ 1 ≤ N ≤ 10^{16}~).

Output

• Gồm T dòng, dòng thứ i chứa kết quả của truy vấn thứ i.

Sample

Input #1

2
1
3

Output #1

5
15

Problem source: Free Contest 45