TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

「噹噹噹噹〜」上課鐘聲無情地響起。
「⼜是數學課啊,可是排列組合什麼的我早就會了,要做什麼好呢 · · · · · · 」⼩希⼼想。
「⼀個正整數的階乘是所有⼩於等於該數之正整數的乘積。⾃然數 n 的階乘寫作 n! 。」
看著課本上關於階乘的介紹,無聊的⼩希嘗試將⼀些階乘寫下來:1! = 1, 2! = 1 × 2 = 2,
3! = 1 × 2 × 3 = 6, 4! = 24, 5! = 120, . . ., 9! = 362880, 10! = 3628800, . . .。寫著寫著,細⼼的⼩希發
現當 n! 的 n 逐漸變⼤的時候,n! 的結尾零的個數也會逐漸變多!
因為⽼師教的內容實在太簡單了,⼩希決定設計更有挑戰性⼀點的問題給⾃⼰:
「存不存在 n 使得 n! 的結尾恰好有 m 個零呢?若有多種可能的 n,那麼最⼩的 n 是多少呢?」

Input Format

輸⼊的第⼀⾏有⼀個整數 T,代表共有幾筆測試資料。
每筆測試資料只有⼀⾏,恰包含⼀個整數 m,代表 n! 結尾零的個數。
• $ 1 \leq T \leq 100000 $
• $ 1 \leq m \leq 10^ 9 $

Output Format

對於每筆測試資料請輸出⼀個正整數 n 於⼀⾏,使得 n! 的結尾恰好有 m 個零。如果有多種可
能的話請輸出最⼩的 n。
如果不存在 n 使得 n! 的結尾恰好有 m 個零,請輸出 −1。

Sample Input

4
1
2
5
10

Sample Output

5
10
-1
45

Hints

Problem Source

NPSC 2015 高中組初賽 pE
Problem Setter: oToToT

Subtasks

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536