Prime Frog

The country prime land can be considered as an infinite quarter plane. The cell in the row x and column y has co-ordinates (x,y). The cell in its lower left corner has co-ordinates (1, 1). A frog lives in this lower left cell. This frog knows some math and he is familiar with n prime numbers. They are P0, P1, . . . , Pn−1. These are called frog prime. Now from the co-ordinate (x, y) the frog can jump to the following co-ordinates (x + y, y), (x, x + y), (|x − y|, y), (x, |x − y|). Also for each frog prime Pi the frog can jump to (x∗Pi,y), (x,y∗Pi). If x is divisible by Pi then it can jump to (x/Pi,y). If y is divisible by Pi then it can jump to (x,y/Pi). A poor farmer in the prime land has a rectangular land. The lower left co-ordinate of this land is (r1,c1) when its upper right co-ordinate is (r2,c2). Each cell of his land can produce 1 unit of corn in each season. But the prime frog is annoying the poor farmer much. Whenever the frog visits a cell it spoils all the corn in that cell. So the poor farmer decided not to cultivate those cells which are reachable by the frog. Help the farmer to maximize the units of corn that he can produce in a season. Input First line of the input contains T (1 ≤ T ≤ 120) the number of test cases. Then T test cases follow. Each test case consists of 2 lines. First line — r1 c1 r2 c2 Second line — n P0 P1 ... Pn−1 1≤r1 ≤r2 ≤106,1≤c1 ≤c2 ≤106. 1 ≤ n ≤ 15. 2≤Pi ≤50andPi isaprimenumber. Output For each test case output contains one line denoting the maximum unit of corn that the farmer can produce in each season. Sample Input 2 2255 12 2255 223 Sample Output 2 1