{p1,...,pk : p1 < p2 < ... < pk} is called a prime k-tuple of distance s if p1,p2,...,pk are consecutive prime numbers and pk − p1 = 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 ∗ 109, 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