시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB223183473441.847%

문제

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+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzQ4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhY3RvcmlhbHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmYWN0b3JpYWwgb2YgYW4gaW50ZWdlciBuLCB3cml0dGVuIG4hLCBpcyB0aGUgcHJvZHVjdCBvZiBhbGwgdGhlIGludGVnZXJzIGZyb20gMSB0aHJvdWdoIG4gaW5jbHVzaXZlLiBUaGUgZmFjdG9yaWFsIHF1aWNrbHkgYmVjb21lcyB2ZXJ5IGxhcmdlOiAxMyEgaXMgdG9vIGxhcmdlIHRvIHN0b3JlIGluIGEgMzItYml0IGludGVnZXIgb24gbW9zdCBjb21wdXRlcnMsIGFuZCA3MCEgaXMgdG9vIGxhcmdlIGZvciBtb3N0IGZsb2F0aW5nLXBvaW50IHZhcmlhYmxlcy4gWW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIHJpZ2h0bW9zdCBub24temVybyBkaWdpdCBvZiBuIS4gRm9yIGV4YW1wbGUsIDUhID0gMSAqIDIgKiAzICogNCAqIDUgPSAxMjAsIHNvIHRoZSByaWdodG1vc3Qgbm9uemVybyBkaWdpdCBvZiA1ISBpcyAyLiBBbHNvLCA3ISA9IDEgKiAyICogMyAqIDQgKiA1ICogNiAqIDcgPSA1MDQwLCBzbyB0aGUgcmlnaHRtb3N0IG5vbi16ZXJvIGRpZ2l0IG9mIDchIGlzIDQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2UgKCZsdDsxNSkuIFRoZSBzaW5nbGUgbGluZSB3aGljaCByZXByZXNlbnRzIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIGFuIGludGVnZXIgbiwgYmV0d2VlbiAxIGFuZCAxMDAwIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0byB0aGUgb3V0cHV0IHRoZSByaWdodG1vc3Qgbm9uLXplcm8gZGlnaXQgb2YgbiEmbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > All-Ukrainian Collegiate Programming Contest > AUCPC Semi-Final 2010 I번