Server Time: Mon Mar 25, 2019 7:44 am
Welcome ( logout
1090 - Trailing Zeroes (II)
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Find the number of trailing zeroes for the following function:

nCr * pq

where n, r, p, q are given. For example, if n = 10, r = 4, p = 1, q = 1, then the number is 210 so, number of trailing zeroes is 1.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains four integers: n, r, p, q (1 ≤ n, r, p, q ≤ 106, r ≤ n).

Output

For each test case, print the case number and the number of trailing zeroes.

Sample Input

Output for Sample Input

2

10 4 1 1

100 5 40 5

Case 1: 1

Case 2: 6

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan