Trailing Zeroes (II)

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

2

10 4 1 1

100 5 40 5

Sample Output

Case 1: 1

Case 2: 6

The question ： seek c(n,r)*p^q Back guide of 0 The number of .

Ideas ： We find the derivative of a number 0 This number is usually factorized to find 2 The number of 5 The number of , Then the smaller one is the end of the number 0 The number of , Because the number required by this question is in the form of division , Because of the molecular 2 And 5 It can be combined with the 2 And 5 Countervailing , So we need 2 Is the number of molecules 2 Subtract the number of from the denominator 2 The number of , seek 5 Is the number of molecules 5 Subtract the number of from the denominator 5 The number of , Then find a smaller one, which is the result , Because the data range of this question is large , So type a watch first , Use prefixes and two-dimensional arrays num【】【】,num【i】【0】 Array to store from 1 To i Medium factor 2 Total number of ,num【i】【1】 Array to store data from 1 To i Medium factor 5 Total number of . Finally, we can get the result by processing , The code is as follows ：

#include<stdio.h>
#include<string>
#include<queue>
#include<math.h>
#define inf 0x3f3f3f3f
#define LL long long
#include<string.h>
#include<algorithm>
using namespace std;
int num[1000010][2]= {0};
void init()
{
    num[1][0]=0;
    num[1][1]=0;
    for(int i=2; i<1000010; i++)
    {
        int x=i;
        num[i][0]=num[i-1][0];
        while(x%2==0)
        {
            num[i][0]++;
            x=x/2;
        }
        int x1=i;
        num[i][1]=num[i-1][1];
        while(x1%5==0)
        {
            num[i][1]++;
            x1=x1/5;
        }
    }
}
int main()
{
    int T,cas=1;
    init();
    int n,r,p,q;
    scanf("%d",&T);
    while(T--)
    {
        int s2,s5;
        scanf("%d %d %d %d",&n,&r,&p,&q);
        s2=num[n][0]-num[r][0]-num[n-r][0]+(num[p][0]-num[p-1][0])*q;
        s5=num[n][1]-num[r][1]-num[n-r][1]+(num[p][1]-num[p-1][1])*q;
        printf("Case %d: ",cas++);
        if(s2>s5)
            printf("%d\n",s5);
        else
            printf("%d\n",s2);
    }
    return 0;
}