시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 644 278 235 45.106%

문제

n!은 정수 n에 대한 팩토리얼 수를 나타내는데, 이는 1부터 n까지의 모든 정수의 곱을 의미한다. 팩토리얼은 굉장히 빨리 커지기 때문에 13!는 대부분의 컴퓨터에서 32비트 정수형을, 70!은 대부분의 부동 소수점 변수의 범위를 넘어선다. 우리는 n!에 대하여 0이 아닌 최우측 수(the rightmost non-zero digit)를 찾으려고 한다. 예를 들어, 5! = 1 * 2 * 3 * 4 * 5 = 120 이므로 5!의 최우측 0이 아닌 수는 2이다. 마찬가지로 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040이며 7!의 0이 아닌 최우측 수는 4가 된다.

입력

첫 줄에 테스트 케이스의 수 t ( 0 < t < 15)가 주어진다. 연속하여 t개의 줄에는 정수 n이 하나씩 주어진다. ( 0 < n < 1001).

출력

n!의 최우측 0이 아닌 수(the rightmost non-zero digit)를 출력하시오.

예제 입력 1

1
5

예제 출력 1

2

힌트

비슷한 문제로 https://www.acmicpc.net/problem/2553가 있다.

W3sicHJvYmxlbV9pZCI6Ijc0ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmMiLCJkZXNjcmlwdGlvbiI6IjxwPm4hXHVjNzQwIFx1YzgxNVx1YzIxOCBuXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmMgXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHVjNzU4IFx1YWNmMVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1ZDMyOVx1ZDFhMFx1YjlhY1x1YzViY1x1Yzc0MCBcdWFkNDlcdWM3YTVcdWQ3ODggXHViZTY4XHViOWFjIFx1Y2VlNFx1YzljMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMTMhXHViMjk0IFx1YjMwMFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM1ZDBcdWMxMWMgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4XHVkNjE1XHVjNzQ0LCA3MCFcdWM3NDAgXHViMzAwXHViZDgwXHViZDg0XHVjNzU4IFx1YmQ4MFx1YjNkOSBcdWMxOGNcdWMyMThcdWM4MTAgXHViY2MwXHVjMjE4XHVjNzU4IFx1YmM5NFx1YzcwNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWMxMjBcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBuIVx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjZDVjXHVjNmIwXHVjZTIxIFx1YzIxOCg8c3Ryb25nPnRoZSByaWdodG1vc3Qgbm9uLXplcm8gZGlnaXQ8XC9zdHJvbmc+KVx1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA1ISA9IDEgKiAyICogMyAqIDQgKiA1ID0gMTIwIFx1Yzc3NFx1YmJjMFx1Yjg1YyA1IVx1Yzc1OCBcdWNkNWNcdWM2YjBcdWNlMjEgMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjMjE4XHViMjk0IDJcdWM3NzRcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyA3ISA9IDEgKiAyICogMyAqIDQgKiA1ICogNiAqIDcgPSA1MDQwXHVjNzc0XHViYTcwIDchXHVjNzU4IDBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1Y2Q1Y1x1YzZiMFx1Y2UyMSBcdWMyMThcdWIyOTQgNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IDxzdHJvbmc+dDxcL3N0cm9uZz4gKCAwICZsdDsgPHN0cm9uZz50PFwvc3Ryb25nPiAmbHQ7IDE1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVmMFx1YzE4ZFx1ZDU1OFx1YzVlYyB0XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggPHN0cm9uZz5uPFwvc3Ryb25nPlx1Yzc3NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoIDAgJmx0OyA8c3Ryb25nPm48XC9zdHJvbmc+ICZsdDsgMTAwMSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+biFcdWM3NTggXHVjZDVjXHVjNmIwXHVjZTIxIDBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzIxOCg8c3Ryb25nPnRoZSByaWdodG1vc3Qgbm9uLXplcm8gZGlnaXQ8XC9zdHJvbmc+KVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmU0NFx1YzJiN1x1ZDU1YyBcdWJiMzhcdWM4MWNcdWI4NWMgPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzI1NTNcIj5odHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC9wcm9ibGVtXC8yNTUzPFwvYT5cdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzQ4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhY3RvcmlhbHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmYWN0b3JpYWwgb2YgYW4gaW50ZWdlciBuLCB3cml0dGVuIG4hLCBpcyB0aGUgcHJvZHVjdCBvZiBhbGwgdGhlIGludGVnZXJzIGZyb20gMSB0aHJvdWdoIG4gaW5jbHVzaXZlLiBUaGUgZmFjdG9yaWFsIHF1aWNrbHkgYmVjb21lcyB2ZXJ5IGxhcmdlOiAxMyEgaXMgdG9vIGxhcmdlIHRvIHN0b3JlIGluIGEgMzItYml0IGludGVnZXIgb24gbW9zdCBjb21wdXRlcnMsIGFuZCA3MCEgaXMgdG9vIGxhcmdlIGZvciBtb3N0IGZsb2F0aW5nLXBvaW50IHZhcmlhYmxlcy4gWW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIHJpZ2h0bW9zdCBub24temVybyBkaWdpdCBvZiBuIS4gRm9yIGV4YW1wbGUsIDUhID0gMSAqIDIgKiAzICogNCAqIDUgPSAxMjAsIHNvIHRoZSByaWdodG1vc3Qgbm9uemVybyBkaWdpdCBvZiA1ISBpcyAyLiBBbHNvLCA3ISA9IDEgKiAyICogMyAqIDQgKiA1ICogNiAqIDcgPSA1MDQwLCBzbyB0aGUgcmlnaHRtb3N0IG5vbi16ZXJvIGRpZ2l0IG9mIDchIGlzIDQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2UgKCZsdDsxNSkuIFRoZSBzaW5nbGUgbGluZSB3aGljaCByZXByZXNlbnRzIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIGFuIGludGVnZXIgbiwgYmV0d2VlbiAxIGFuZCAxMDAwIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0byB0aGUgb3V0cHV0IHRoZSByaWdodG1vc3Qgbm9uLXplcm8gZGlnaXQgb2YgbiEmbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=