시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 721 318 269 47.611%

문제

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

출력

각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.

예제 입력 1

6
3
60
100
1024
23456
8735373

예제 출력 1

0
14
24
253
5861
2183837
W3sicHJvYmxlbV9pZCI6IjM0NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNTBcdWMyMThcdWFjMDAgXHViNDFjIFx1ZDYwNFx1YzZiMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzU4IFx1ZDBiOVx1YWMxM1x1YzgxY1x1YjEwOFx1YjdmNFx1YzVlMFx1ZDM3Y1x1YjdlY1x1YjljOFx1YzgxY1x1YzJhNFx1ZDJmMFx1Y2RhOVx1YmIzNFx1YWNmNVx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YjljOFx1YzJhNFx1ZDEzMCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVhZDUwXHVjMjE4XHViODVjIFx1Y2RlOFx1Yzc4NFx1ZDU1OFx1YzYwMFx1YjJlNCE8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMDk4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1YzVkMFx1YWM4YyBcdWQwNmNcdWIwOThcdWQwNzAgXHVhZTMwXHViMzAwXHViOTdjIFx1ZDQ4OFx1YWNlMCBcdWNjYWIgXHVjMjE4XHVjNWM1XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMxNFx1YjM1OCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNTQ0XHViYjM0XHViM2M0IFx1YzY3OFx1ZDMxMFx1YzZkMCBcdWMyMWNcdWQ2OGMgXHViYjM4XHVjODFjKFRyYXZlbGluZyBTYWxlc21hbiBQcm9ibGVtLCBUU1ApXHViOTdjIFx1ZDQ4MFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmNmNFx1YWNlMCBcdWIwOTlcdWMyZWNcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWM2NDBcdWM5MTFcdWM1ZDAgXHVkNTU5XHVjMGRkIFx1YjBhOFx1YWRkY1x1YjI5NCBUU1BcdWI5N2MgXHVjNjQ0XHVjODA0XHVkMGQwXHVjMGM5XHVjNzNjXHViODVjIFx1ZDQ4MFx1YjgyNFx1YWNlMCBcdWQ1NThcdWM2MDBcdWFjZTAsIFx1ZDYwNFx1YzZiMFx1YjI5NCBcdWFkZjhcdWFjNzggXHViY2Y0XHVhY2UwIFx1YWNiZFx1YzU0NVx1Yzc0NCBcdWFlMDhcdWNlNTggXHViYWJiXHVkNTVjXHViMmU0LiBcdWM2NWNcdWIwZDBcdWJhNzQgVFNQXHViOTdjIFx1YzY0NFx1YzgwNFx1ZDBkMFx1YzBjOVx1YzczY1x1Yjg1YyBcdWQ0ODBcdWI4MjRcdWJhNzQgTyhOISlcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzE4Y1x1YmFhOFx1YjQxOFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IFx1YWNiZFx1YzU0NVx1Yzc0NCBcdWFlMDhcdWNlNTggXHViYWJiXHVkNTYwIFx1YzJkY1x1YWMwNFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjA5OCBcdWIwYThcdWFkZGNcdWIyOTQgTyhOISlcdWM3NzQgXHVjNjVjIFx1ZDA3MFx1YzljMFx1YjNjNCBcdWM3OTggXHViYWE4XHViOTc4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVkNjA0XHVjNmIwXHViMjk0IFx1YjM1NFx1YjM1NFx1YzZiMSBcdWFjYmRcdWM1NDVcdWM3NDQgXHVhZTA4XHVjZTU4IFx1YmFiYlx1ZDU1OFx1YWNlMCwgTiFcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1ZDA3MFx1YzljMCBcdWIzMDBcdWI3YjVcdWM4MDFcdWM3M2NcdWI4NWNcdWIwOThcdWI5YzggXHVjNTRjXHViODI0XHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IE4hXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWIwNWRcdWM1ZDAgXHVjNzg4XHViMjk0IDBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjA5OCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVhY2JkXHVjNTQ1XHVjNzQ0IFx1YWUwOFx1Y2U1OCBcdWJhYmJcdWQ1NThcdWM1ZWMgXHVjOWMwXHVhZTA4IFx1Y2Y1NFx1YjUyOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NzRcdWIyZTQuIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWQ2MDRcdWM2YjBcdWI5N2MgXHViMzAwXHVjMmUwXHVkNTU4XHVjNWVjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWM3NzRcdWM1YjRcdWMxMWMgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDEgJmx0Oz0gTiAmbHQ7PSAxMDAwMDAwMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IE4hXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWIwNWRcdWM1ZDAgXHVjNzg4XHViMjk0IDBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFjdG9yaWFsIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbW9zdCBpbXBvcnRhbnQgcGFydCBvZiBhIEdTTSBuZXR3b3JrIGlzIHNvIGNhbGxlZCBCYXNlIFRyYW5zY2VpdmVyIFN0YXRpb24gKEJUUykuIFRoZXNlIHRyYW5zY2VpdmVycyBmb3JtIHRoZSBhcmVhcyBjYWxsZWQgY2VsbHMgKHRoaXMgdGVybSBnYXZlIHRoZSBuYW1lIHRvIHRoZSBjZWxsdWxhciBwaG9uZSkgYW5kIGV2ZXJ5IHBob25lIGNvbm5lY3RzIHRvIHRoZSBCVFMgd2l0aCB0aGUgc3Ryb25nZXN0IHNpZ25hbCAoaW4gYSBsaXR0bGUgc2ltcGxpZmllZCB2aWV3KS4gT2YgY291cnNlLCBCVFNlcyBuZWVkIHNvbWUgYXR0ZW50aW9uIGFuZCB0ZWNobmljaWFucyBuZWVkIHRvIGNoZWNrIHRoZWlyIGZ1bmN0aW9uIHBlcmlvZGljYWxseS48XC9wPlxyXG5cclxuPHA+QUNNIHRlY2huaWNpYW5zIGZhY2VkIGEgdmVyeSBpbnRlcmVzdGluZyBwcm9ibGVtIHJlY2VudGx5LiBHaXZlbiBhIHNldCBvZiBCVFNlcyB0byB2aXNpdCwgdGhleSBuZWVkZWQgdG8gZmluZCB0aGUgc2hvcnRlc3QgcGF0aCB0byB2aXNpdCBhbGwgb2YgdGhlIGdpdmVuIHBvaW50cyBhbmQgcmV0dXJuIGJhY2sgdG8gdGhlIGNlbnRyYWwgY29tcGFueSBidWlsZGluZy4gUHJvZ3JhbW1lcnMgaGF2ZSBzcGVudCBzZXZlcmFsIG1vbnRocyBzdHVkeWluZyB0aGlzIHByb2JsZW0gYnV0IHdpdGggbm8gcmVzdWx0cy4gVGhleSB3ZXJlIHVuYWJsZSB0byBmaW5kIHRoZSBzb2x1dGlvbiBmYXN0IGVub3VnaC4gQWZ0ZXIgYSBsb25nIHRpbWUsIG9uZSBvZiB0aGUgcHJvZ3JhbW1lcnMgZm91bmQgdGhpcyBwcm9ibGVtIGluIGEgY29uZmVyZW5jZSBhcnRpY2xlLiBVbmZvcnR1bmF0ZWx5LCBoZSBmb3VuZCB0aGF0IHRoZSBwcm9ibGVtIGlzIHNvIGNhbGxlZCAmcXVvdDtUcmF2ZWxsaW5nIFNhbGVzbWFuIFByb2JsZW0mcXVvdDsgYW5kIGl0IGlzIHZlcnkgaGFyZCB0byBzb2x2ZS4gSWYgd2UgaGF2ZSBOIEJUU2VzIHRvIGJlIHZpc2l0ZWQsIHdlIGNhbiB2aXNpdCB0aGVtIGluIGFueSBvcmRlciwgZ2l2aW5nIHVzIE4hIHBvc3NpYmlsaXRpZXMgdG8gZXhhbWluZS4gVGhlIGZ1bmN0aW9uIGV4cHJlc3NpbmcgdGhhdCBudW1iZXIgaXMgY2FsbGVkIGZhY3RvcmlhbCBhbmQgY2FuIGJlIGNvbXB1dGVkIGFzIGEgcHJvZHVjdCAxLjIuMy40Li4uLk4uIFRoZSBudW1iZXIgaXMgdmVyeSBoaWdoIGV2ZW4gZm9yIGEgcmVsYXRpdmVseSBzbWFsbCBOLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvZ3JhbW1lcnMgdW5kZXJzdG9vZCB0aGV5IGhhZCBubyBjaGFuY2UgdG8gc29sdmUgdGhlIHByb2JsZW0uIEJ1dCBiZWNhdXNlIHRoZXkgaGF2ZSBhbHJlYWR5IHJlY2VpdmVkIHRoZSByZXNlYXJjaCBncmFudCBmcm9tIHRoZSBnb3Zlcm5tZW50LCB0aGV5IG5lZWRlZCB0byBjb250aW51ZSB3aXRoIHRoZWlyIHN0dWRpZXMgYW5kIHByb2R1Y2UgYXQgbGVhc3Qgc29tZSByZXN1bHRzLiBTbyB0aGV5IHN0YXJ0ZWQgdG8gc3R1ZHkgYmVoYXZpb3VyIG9mIHRoZSBmYWN0b3JpYWwgZnVuY3Rpb24uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGV5IGRlZmluZWQgdGhlIGZ1bmN0aW9uIFouIEZvciBhbnkgcG9zaXRpdmUgaW50ZWdlciBOLCBaKE4pIGlzIHRoZSBudW1iZXIgb2YgemVyb3MgYXQgdGhlIGVuZCBvZiB0aGUgZGVjaW1hbCBmb3JtIG9mIG51bWJlciBOIS4gVGhleSBub3RpY2VkIHRoYXQgdGhpcyBmdW5jdGlvbiBuZXZlciBkZWNyZWFzZXMuIElmIHdlIGhhdmUgdHdvIG51bWJlcnMgTjEmbHQ7TjIsIHRoZW4gWihOMSkgJmx0Oz0gWihOMikuIEl0IGlzIGJlY2F1c2Ugd2UgY2FuIG5ldmVyICZxdW90O2xvc2UmcXVvdDsgYW55IHRyYWlsaW5nIHplcm8gYnkgbXVsdGlwbHlpbmcgYnkgYW55IHBvc2l0aXZlIG51bWJlci4gV2UgY2FuIG9ubHkgZ2V0IG5ldyBhbmQgbmV3IHplcm9zLiBUaGUgZnVuY3Rpb24gWiBpcyB2ZXJ5IGludGVyZXN0aW5nLCBzbyB3ZSBuZWVkIGEgY29tcHV0ZXIgcHJvZ3JhbSB0aGF0IGNhbiBkZXRlcm1pbmUgaXRzIHZhbHVlIGVmZmljaWVudGx5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgaXMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBUIG9uIHRoZSBmaXJzdCBsaW5lIG9mIGlucHV0LiBJdCBzdGFuZHMgZm9yIHRoZSBudW1iZXIgb2YgbnVtYmVycyB0byBmb2xsb3cuIFRoZW4gdGhlcmUgaXMgVCBsaW5lcywgZWFjaCBjb250YWluaW5nIGV4YWN0bHkgb25lIHBvc2l0aXZlIGludGVnZXIgbnVtYmVyIE4sIDEgJmx0Oz0gTiAmbHQ7PSAxMDAwMDAwMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSBudW1iZXIgTiwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgc2luZ2xlIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIFooTikuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d