You’ve been given an assorted set of gears. Each gear has a different number of teeth – the notches on a gear that interlock with notches on another gear to transmit speed. You have a couple of belts one coupled to an input and the other for the output. You are given the rpm of the input belt Si and a minimum value So (where So > Si) so that you can increasethe speed via a system of gears as shown above

You need to figure out all the possible pairs of gears that can be used to achieve an output rpm >= So.

Input

The input is specified in a file containing test-cases.

·        The first line contains the number of gearsthat are available to you, g.

·        The next line contains g numbers indicating the number of teeth on each gear, separated by spaces.

·        The next line contains the number of test cases – n

o       This is followed by n test cases. Each test case is specified by 2 speed values on a single line. (So here the first test case specifies that you need to design a gear-system that increases Si = 50 rpm to a value above 200 rpm)

7

20 10 4 6 40 25 100

2

50 200

35 75

Output

9

15

E.g. for raising the speed from 50 to 200, any of the following 9 pairs can be used

 [100, 6] [40, 6] [25, 6] [25, 4] [20, 4] [40, 4] [100, 4] [100, 20] [100, 10]