405553: GYM101992 A Zeros and Ones

Memory Limit:1024 MB Time Limit:15 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Zeros and Onestime limit per test15 secondsmemory limit per test1024 megabytesinputzeros.inoutputstandard output

Given four integers x, y, M and K. You need to count the number of integers d that satisfy the following rules:

  1. The binary representation of d should consist of x ones and y zeroes without leading zeros.
  2. d modulo M is greater than or equal to K.
Input

The first line of the input is the number of test cases T. Each test case consists of four integers x, y, M and K, where 1 ≤ M ≤ 109, 1 ≤ x + y ≤ 42, x ≥ 1, y ≥ 0 and 0 ≤ K < M.

Output

For each test case output a single line with the number of integers d that satisfy the rules.

ExampleInput
1
2 2 8 2
Output
2

加入题单

上一题 下一题 算法标签: