Problem B
Prime Frog
Input: Standard Input

Output: Standard Output

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 P₀, P₁… P_n-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 P_i the frog can jump to (x*P_i, y), (x ,y*P_i). If x is divisible by P_i then it can jump to (x/P_i, y). If y is divisible by P_i then it can jump to (x, y/P_i).

A poor farmer in the prime land has a rectangular land. The lower left co-ordinate of this land is (r₁, c₁) when its upper right co-ordinate is (r₂,c₂). 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 – r₁ c₁ r₂ c₂

Second line – n P₀ P₁ …. P_n-1

1≤r₁≤r₂≤10^6, 1≤c₁≤c₂≤10^6.

1≤n≤15.

2≤P_i≤50 and P_i is a prime number.

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 Output for Sample Input

2 2 2 5 5 1 2 2 2 5 5 2 2 3

2 1

---

Problem-setter: Abdullah al Mahmud

Special Thanks: Derek Kisman