교수가 된 현우

알고리즘의 대가 현우가 교수로 취임하였다!

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

그때 학생 남규가 TSP를 완전 탐색으로 풀려고 하는 것을 보고 현우는 크게 놀랐다. TSP를 완전 탐색으로 풀면 $O(N!)$의 시간이 걸리는데, 이는 감당할 수 없을 만큼 큰 시간이기 때문이다.

그러나 남규는 $O(N!)$이 왜 그렇게 큰지 잘 모른다. 그래서 현우는 $N!$이 얼마나 큰지 대략이나마 알려 주기 위해, 자연수 $N$이 주어지면 $N!$의 오른쪽 끝에 붙어 있는 $0$의 개수를 계산해 알려 주기로 하였다.

지금 현우는 너무 놀라 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 정수 $N$이 하나씩 주어진다 ($1 \le N \le 1\,000\,000\,000$).

각 테스트 케이스마다 한 줄에 $N!$의 오른쪽 끝에 붙어 있는 $0$의 개수를 출력한다.