注意

この問題の実行時間制限は 3.000 秒です。

問題文

$Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは、正整数 $L_i, R_i$ が与えられるので、次の【問題】の答えを求めてください。

【問題】

• まず、机の上に $L_i, L_i+1, \cdots, R_i$ が書かれたカードがそれぞれ $1$ 枚ずつ置かれている。その後、机の上にカードが $1$ 枚以上置かれている間、シャキーンさんは次の操作を繰り返す。
• 机の上に置かれたカードの中で書かれた値が最も小さいものを選び、その値を $k$ とする。シャキーンさんはそのカードを食べる。
• その後、机の上に置かれたカードの中で $k$ の倍数の値が書かれたものをすべて机の上から取り除く。取り除いたカードは食べないこととする。

制約

• 入力はすべて整数
• $1 \le Q \le 2 \times 10^5$
• $1 \le L_i \le R_i \le 10^6$ $(1\le i\le Q)$

入力

$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

出力

$Q$ 行出力せよ。 $i$ $(1\le i\le Q)$ 行目には、 $i$ 番目のクエリに対する答えを出力せよ。

サンプル

5
1 20
2 20
3 20
4 20
5 20

1
8
8
9
9

5
12 345678
2025 870777
100000 1000000
1000000 1000000
1 1

29639
100000
338570
1
1