You are given an an infinite box of bricks where each brick has dimension ~a \times b~. By placing bricks side by side, you can construct a rectangle.

You are asked to construct a series of ~n~ rectangles. Each rectangle must have some length-to-width ratio ~1:m_i~. For each rectangle, determine the minimum number of bricks you'd need to construct such a rectangle.

Input

The first line contains an integer ~n~, the number of rectangles you need to construct.

The second line contains two space-integers ~a~ and ~b~ representing the dimensions of the bricks.

The next ~n~ lines each contain a single integer ~m_i~ representing the ratio of the rectangle you need to construct.

Output

For each ~1 \le i \le n~, output the minimum number of bricks needed to construct a rectangle with a length-to-width ratio of ~1:m_i~.

Constraints

• ~1 \le a,b \le 1000~
• ~1 \le m \le 10^9~

Example 1

Input

3
2 3
1
2
5

Output

6
3
30

Explanation

Each brick has dimension ~2 \times 3~.

The first query 1 asks you to construct a rectangle with a length-to-width ratio of ~1:1~. We can do this with 6 bricks:

111222
111222
333444
333444
555666
555666

where each distinct number represents a particular brick (for example, all the 1s represent the first brick). This resulting rectangle has dimension ~6 \times 6~, which is in a ~1:1~ ratio.