Por Costel the pig has found a legendary safe. It is said that it "holds so much food that a man may feast on it for countless years". He thinks it might be enough for breakfast.
However, he must first bypass its security mechanism which is very similar(surprisingly) to that of a suitcase.
In order to open the safe, one must insert a code of length 
( digits from 
to 
). The code is inserted by the means of small wheels. These can be turned upward or downward. If a wheel indicates value 
, it can be moved upward to indicate value 
mod 
, or it can be moved downward to indicate value 
mod .
The legend says that the safe was crafted by 
elder pigs. That is why there exist distinct codes that open the safe. Also, the safe has deteriorated with the passing of time and now every wheel has an "error margin" given by a number 
. This means that a code 
will open the safe if there exists at least one code 
out of th elder pig codes such that 
for any 
in the range 
, where
means the minimum number of wheel turns in order to get from digit 
to digit 
means the -th digit of code .
Given that the system was designed by pigs, it was to be expected that it's not top-notch. There are many codes that open the safe. SO many in fact, that if one were to count them, he would have to do so mod 
. Calculate this value! Por Costel can't hold his appetite much longer!
The input file cifrul.in will contain on its first line an integer 
(
), the number of tests. On the following lines, each test will be described by the following:
The first line of a test case contains four integer numbers (
), (
), 
and (
).
The next lines will each contain integer numbers. These will be the codes of the elder pigs. The -th line describes the -th code.
Print 
lines in the file cifrul.out. The -th line should contain the answer for the -th test case.
2
1 2 10000 3
1
6
3 1 100 5
1 6 30
12
1331
