{p₁,..., p_k : p₁ < p₂ <...< p_k} is called a prime k -tuple of distance s if p₁, p₂,..., p_k are consecutive prime numbers and p_k - p₁ = s . For example, with k = 4 , s = 8 , {11, 13, 17, 19} is a prime 4-tuple of distance 8.

Given an interval [a, b] , k , and s , your task is to write a program to find the number of prime k -tuples of distance s in the interval [a, b] .

Input 

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, there is only one line containing 4 numbers, a , b , k and s (a, b < 2 * 10⁹, k < 10, s < 40) .

Output 

For each test case, write in one line the numbers of prime k -tuples of distance s .

Sample Input 

1
100 200 4 8

Sample Output 

2