A - Ribbon Cut Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は手芸クラブの部長です。文化祭の準備として、N 本のリボンをそれぞれ決められた長さに切り分けて、飾り付け用のパーツを作ることになりました。

i 番目のリボンの長さは L_i ミリメートルで、パーツ1つあたりの指定された長さは T_i ミリメートルです。各リボンについて、一方の端から順に T_i ミリメートルずつ切り出していきます。こうして得られるパーツの個数は \lfloor L_i / T_i \rfloor 個であり、切り出した後に残る切れ端の長さは R_i = L_i \bmod T_i ミリメートルです。

顧問の青木先生は「切れ端が残っていて（R_i > 0）、かつその長さが指定された長さの半分以上、すなわち R_i \geq \lfloor T_i / 2 \rfloor を満たすならば、その切れ端も1つのパーツとして使ってよい」というルールを設けています。

まとめると、i 番目のリボンから得られるパーツの個数 P_i は次のように決まります。

P_i = \begin{cases} \lfloor L_i / T_i \rfloor + 1 & \text{（} R_i > 0 \text{ かつ } R_i \geq \lfloor T_i / 2 \rfloor \text{ の場合）} \\ \lfloor L_i / T_i \rfloor & \text{（それ以外の場合）} \end{cases}

ここで「それ以外の場合」とは、切れ端が残らない場合（R_i = 0）、または切れ端が残るが長さが \lfloor T_i / 2 \rfloor に満たない場合（0 < R_i < \lfloor T_i / 2 \rfloor）のいずれかです。

なお、L_i < T_i の場合にもこのルールは同様に適用されます。この場合 \lfloor L_i / T_i \rfloor = 0 であり、リボン全体が長さ R_i = L_i の切れ端となります。切れ端の長さが \lfloor T_i / 2 \rfloor 以上であればパーツ1個が得られ、そうでなければパーツは0個です。

N 本のリボンについて、それぞれ得られるパーツの個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq 10^{18}
  • 1 \leq T_i \leq 10^{18}
  • 入力はすべて整数である。

入力

N
L_1 T_1
L_2 T_2
\vdots
L_N T_N

1 行目には、リボンの本数を表す整数 N が与えられる。続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目のリボンの長さ L_i と指定されたパーツの長さ T_i が、スペース区切りで与えられる。

出力

N 行出力せよ。i 行目（1 \leq i \leq N）には、i 番目のリボンから得られるパーツの個数を出力せよ。

入力例 1

5
10 3
10 5
7 4
7 5
7 6

出力例 1

4
2
2
2
1

入力例 2

5
5 3
4 3
3 7
2 7
100 100

出力例 2

2
2
1
0
1

入力例 3

8
1000 300
1000 400
999 500
123456 789
50 99
50 100
50 101
1 1

出力例 3

3
3
2
156
1
1
1
1

入力例 4

10
1000000000000000000 1
1000000000000000000 3
999999999999999999 2
1000000000000000000 1000000000000000000
999999999999999999 1000000000000000000
500000000000000000 1000000000000000000
499999999999999999 1000000000000000000
7 2
123456789012345678 987654321
1000000000000000000 7

出力例 4

1000000000000000000
333333333333333334
500000000000000000
1
1
1
0
4
124999999
142857142857142857

入力例 5

6
1 1
1 2
1 3
1 1000000000000000000
1000000000000000000 1000000000000000000
2 1

出力例 5

1
1
1
0
1
2

Score : 233 pts

Problem Statement

Takahashi is the president of the handicrafts club. As preparation for the cultural festival, he needs to cut N ribbons into specified lengths to make decorative parts.

The i-th ribbon has a length of L_i millimeters, and the specified length per part is T_i millimeters. For each ribbon, parts of T_i millimeters are cut out sequentially from one end. The number of parts obtained this way is \lfloor L_i / T_i \rfloor, and the length of the leftover scrap after cutting is R_i = L_i \bmod T_i millimeters.

The advisor, Teacher Aoki, has established the following rule: "If there is a remaining scrap (R_i > 0) and its length is at least half of the specified length, that is, R_i \geq \lfloor T_i / 2 \rfloor, then that scrap may also be used as one part."

In summary, the number of parts P_i obtained from the i-th ribbon is determined as follows:

P_i = \begin{cases} \lfloor L_i / T_i \rfloor + 1 & \text{(if } R_i > 0 \text{ and } R_i \geq \lfloor T_i / 2 \rfloor \text{)} \\ \lfloor L_i / T_i \rfloor & \text{(otherwise)} \end{cases}

Here, "otherwise" refers to either the case where no scrap remains (R_i = 0), or the case where a scrap remains but its length is less than \lfloor T_i / 2 \rfloor (0 < R_i < \lfloor T_i / 2 \rfloor).

Note that this rule applies in the same way even when L_i < T_i. In this case, \lfloor L_i / T_i \rfloor = 0, and the entire ribbon becomes a scrap of length R_i = L_i. If the scrap length is at least \lfloor T_i / 2 \rfloor, then one part is obtained; otherwise, zero parts are obtained.

For each of the N ribbons, determine the number of parts obtained.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq 10^{18}
  • 1 \leq T_i \leq 10^{18}
  • All input values are integers.

Input

N
L_1 T_1
L_2 T_2
\vdots
L_N T_N

The first line contains an integer N representing the number of ribbons. Each of the following N lines, where the i-th line (1 \leq i \leq N), contains the length L_i of the i-th ribbon and the specified part length T_i, separated by a space.

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain the number of parts obtained from the i-th ribbon.

Sample Input 1

5
10 3
10 5
7 4
7 5
7 6

Sample Output 1

4
2
2
2
1

Sample Input 2

5
5 3
4 3
3 7
2 7
100 100

Sample Output 2

2
2
1
0
1

Sample Input 3

8
1000 300
1000 400
999 500
123456 789
50 99
50 100
50 101
1 1

Sample Output 3

3
3
2
156
1
1
1
1

Sample Input 4

10
1000000000000000000 1
1000000000000000000 3
999999999999999999 2
1000000000000000000 1000000000000000000
999999999999999999 1000000000000000000
500000000000000000 1000000000000000000
499999999999999999 1000000000000000000
7 2
123456789012345678 987654321
1000000000000000000 7

Sample Output 4

1000000000000000000
333333333333333334
500000000000000000
1
1
1
0
4
124999999
142857142857142857

Sample Input 5

6
1 1
1 2
1 3
1 1000000000000000000
1000000000000000000 1000000000000000000
2 1

Sample Output 5

1
1
1
0
1
2