There is a person named Bob who is the mayor of a state. He wants to find the maximise number of vehicles that can be registered in his state.

A vehicle normally has a registration number like ST 01 AB 1234. Each registration number has four parts, separated by spaces. The first part has two letters common for all cars in the state. The next two-digit number is the number of the district where the car is registered within the state. It is always two digits and may have a leading zero. After that, the next part consists of two letters (AB), with each letter selected from a range, denoting the series and the last part is a 4-digit number this will always be four digits, even if it has leading zeros).

The entire registration number is unique to each vehicle. You have been given the number of districts in the state, a range of letters to be used in the series and a set of digits that can be used for forming a vehicle registration number.

Your task is to find the maximum number of vehicles that can be registered in Bob’s state.

Note :

1. No two vehicles can have the same registration number. 
2. Two registration numbers are said to be different if they have at least a different character or a digit at the same location. For eg. DL 05 AC 1234 and DL 05 AC 1235 are different, DL 05 AC 1234 and DL 05 AB 1234 are different registration numbers. 
3. All the cars will have the same first two characters as they have to be registered in the same state.
4. The numbering of the districts in the state starts from ‘1’ (which will obviously be written as 01 in registration number).

Input Format :

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains a single integer 'districtCount', denoting the number of districts in the state.

The second line of each test case contains four space-separated characters 'ALPHA1', 'ALPHA2', 'ALPHA3' and 'ALPHA4' , denoting the range of the first alphabet and second alphabet of the series. The range for first and the second alphabet will be [ALPHA1, ALPHA2] and [ALPHA3, ALPHA4] respectively.

The third line of each test case contains four space-separated integers 'DIG1', 'DIG2', 'DIG3' and 'DIG4' denoting the range of last 4 digits in the vehicle registration number. The ranges will be [0, DIG1], [0, DIG2], [0, DIG3] and [0, DIG4] respectively. 

Output Format :

The only line of output of each test case consists of an integer, the maximum number of vehicles that can be registered in the state.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10^4
1 <= Number of districts < 10^2
A <= Range of alphabets <= Z
0 <= Range of digits <= 9
ALPHA1 <= ALPHA2 and ALPHA3 <= ALPHA4

The width of the district column will always be equal to 2.

Time Limit: 1 sec.