#1992 J 의 핑크빛 캠퍼스 라이프

33  1 s   128 MB  

Description

 

지옥 같은 남고 생활을 마치고 드디어 대학에 입학한 J 는 잔뜩 들떠있었다.
핑크빛 캠퍼스 라이프를 꿈꾸던 J 는 여자친구를 사귀기 위해서는 돈이 필요하다는 것을 알게 되었다.
밥 먹을 때도 돈, 영화 볼 때도 돈, 심지어 간단히 만나 커피한잔 할 때도 돈 만원은 우습게 깨졌다. 이제 성인인데 차마 집에서 용돈을 받기 미안한 J 는 알바를 구하기로 마음먹었다. 무슨
일을 할까 고민하던 끝에 고등학교 때부터 수학만큼은 자신 있던 J 는 신의 알바, 과외를 하기로결심했다.
그래도 막상 가르치려니 조금 소심해진 J 는 고등학생보단 중학생 과외를 선택했고 온 동네에 전단지를 붙여 과외를 시작했다.
긴장되는 과외 첫날, J 의 긴장감과는 다르게 과외는 수월하게 진행되었고 과외가 끝나갈 무렵 학생이 숙제가 있는데 모르겠다며 질문했다.
숙제는 팩토리얼에 관한 문제였는데 n! / m!을 하고 몫의 마지막 '0'의 개수를 세는 문제였다.
'별 것 아니군'이라고 생각하며 다음 문제를 쳐다본 J 는 마음이 얼어붙는 것을 느꼈다.
 
'아, 이 학교선생님은 성격이 안 좋은 것이 분명해.'
 
맙소사, 무려 n 과 m 이 수십만에 달하는 문제들이 아래 줄줄이 있는 것이었다. 하지만 수학에 상당한 프라이드가 있는 J 는 차마 첫 시간부터 못한다는 말을 할 수 없었다. 그래서 과외 전
준비해온 멘트를 치기 시작했다.
 
"음... 푸는데 시간이 좀 걸릴 것 같은데 선생님이 알아보고 다음시간에 와서 풀어줄게. ^^"
 
과외학생은 미심쩍은 표정을 감추지 못하며 알았다고 대답했고, 집으로 돌아온 J 는 미친듯한
고민에 휩쌓였다.
 
'아... 이걸 어떻게 한담...'
 
J 의 핑크빛 캠퍼스 라이프를 위해 우리가 조금 도와주자.
문제는 n!을 m!로 나눈 몫의 뒤에 붙은 연속적인 '0'의 개수를 세어주는 것이다. 예를들어 n 이 5, m 이 2 일때는 5!/2! = (5*4*3*2*1) / (2*1) = 60, 마지막 '0'의 개수는 1 개이다.
 

Input

 

테스트 케이스 $Testcase$ 가 입력된다.$( 1 \leq TestCase \leq 100 )$
각 테스트 케이스마다 $m, n$ 가 입력이된다. $( 1 \leq n \leq m \leq 10^8 )$

Output

마지막 ‘0’의 개수

Sample Input

Sample Output

3
5 2
100 99
10 9
1
2
1

Source

2012 Ajou Programming Contest, Division 2