문제 설명
자연수의 나라에서 수들이 살고 있습니다. 오늘은 배수에 대해 열띠게 토론하고 있습니다.
1의 배수는 1, 2, 3, ... 등이 있습니다.
2의 배수는 2, 4, 6, ... 등이 있습니다.
3의 배수는 3, 6, 9, ... 등이 있습니다.
자연수들은 1부터 k까지 연속된 모든 자연수의 배수에 해당하는 가장 작은 수 x가 궁금해졌습니다.
예를 들어 1, 2, 3의 배수에 해당하는 수는 6, 12, 18, ... 등이 있지만 그 중 가장 작은 수는 6입니다.
1, 2, 3, ..., 10의 배수에 해당하는 가장 작은 수는 2520입니다.
x를 직접 구할 수 있으면 좋겠지만 k가 조금만 커져도 x의 크기는 너무나도 커지기 때문에 자연수들은 다른 방법으로 접근하려고 합니다.
그렇게 고민 끝에 생각한 것은, k가 주어지면 x의 끝에 붙는 연속된 0의 개수라도 구해서 x의 크기를 짐작하는 것이었습니다.
자연수들의 궁금증을 해결해주세요!
입력 설명
첫 줄에 전체 테스트 케이스 T (1<= T <= 100)가 주어지며, 그 다음 줄부터는 다음의 규칙으로 입력이 주어진다.
각 테스트 케이스에는 자연수 k가 주어지며, k의 범위는 1 이상 1,000,000,000 이하이다.
출력 설명
각 줄마다 1부터 k까지 연속된 모든 자연수의 배수에 해당하는 가장 작은 자연수 x의 끝에 붙는 연속된 0의 개수를 출력한다.