High School Programming League Problems Archive

You have to transport a cube by a distance of S meters. The edge of the cube is A meters long and the cube weighs M kilograms. S is a multiple of A. One can proceed in two ways:

1. by rolling the box along its edges (fighting gravity)
2. by pushing it along one of its square faces (fighting friction)

You are given the coefficient of friction F and have to decide which way is better.

Input

Standard input contains N (1 ≤ N ≤ 60 000) lines, each containing four values A, M, S, F (10 ≤ A, M, S ≤ 30 000; 0.001 ≤ F ≤ 1.000)) separated by spaces. In line N+1 there are four zeros separated by spaces. Do not process this test case.

Output

Write N lines to standard output. Each should contain a single number 1 if less work is done when rolling the box and 2 if less work is done when pushing it. You are guaranteed that the difference between the works counted in both ways will never be closer than 1% of the larger of the considered values. You can assume the following value of gravitational acceleration: g=9.80665.

Example

Input:
10 50 10 0.2
20 40 60 0.3
30 100 30 0.4
0 0 0 0.0
Output:
2
1
1

Scoring

For solving this problem you will score 10 points.