Explosive Increasing Sequence

2 secs 1024 MB
sgsw

問題文


以下のようにして構成される数列があります。

・初め、である。

として帰納的に定義する。

・これを無限回繰り返して得られるとする。

すなわち、です。

自然数が与えられます。

以下の個のクエリに回答してください。

番目のクエリでは自然数が与えられる。

における番目から番目までの項に含まれる以上以下の数の個数を求めよ。

入力


Q
L_1 R_1 X_1 Y_1
L_2 R_2 X_2 Y_2
...
L_Q R_Q X_Q Y_Q

出力


行にわたって出力してください。

行目には番目のクエリの個数を出力してください。

最後に改行してください。

制約


サンプル


入力1
5
1 5 1 2
1 5 2 4
1 5 1 1
1 5 4 5
1 8 4 4
出力1
4
2
3
0
1

前述の通り、です。

番目から番目までの数列の要素のうち、以上以下のものは番目の個あります。

番目から番目までの数列の要素のうち、以上以下のものは番目の個あります。

番目から番目までの数列の要素のうち、以上以下のものは番目の個あります。

番目から番目までの数列の要素のうち、以上以下のものは個です。

番目から番目までの数列の要素のうち、以上以下のものは番目のつあります。

入力2
5
12345 67890 3 4
12345 67890 1 4
12345 67890 4 5
12345 67890 1 3
12345 67890 5 5
出力2
10414
52074
5207
48603
1736
入力3
1
1 1 1 1
出力3
1
入力4
4
998244353 998244353 1 3
998244353 998244353 2 12
998244353 998244353 3 123
998244353 998244353 4 1234
出力4
1
0
0
0

Submit


Go (1.14)