A. Zeros and Ones
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
zeros.in
output
standard 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.

Example
Input
1
2 2 8 2
Output
2