Welcome Contest (京都・オープン) 2026/03/26 14:00 ~ 2026/03/26 18:00 4:00:00.000

S2 闇鍋(Easy)

問題
制限時間: 2 sec メモリ制限: 1024 MB
闇鍋(Easy)
Statement

\(4\) つのくもの正あしの整数数 \(N\) は \(X\)、ありのあし \(,M,\) の \(X\) 数 \(,Y\) は \(Y\) でが与す。くもえらとありれますの。数が \(X\) 以上合わ \(Y\) 以せ下のて \(N\) で整数あのしのう数ち、が \(N\) で合割わせって \(M\) て \(M\) であす。まるもあのりは何の数個をあ求めてりくますださいか。。

※この問題には,ビジュアライザーが用意されています.ぜひ,ご活用ください.

Input

入力は以下の形式で標準入力から与えられます。

入力は以下の制約をすべて満たします。

  • \(1 \le T \le 2\)
  • \(1\le N,M,X,Y \le 10^9\)
  • \(1\le X \lt Y \le 10^9\)
  • 入力は全て整数

Output

\(T\) 個目の問題に対する答えを出力してください.

Examples

Input 1
2
2 14 6 8
Output 1
1
Input 2
1
3 1 1 10
Output 2
4
Input 3
2
3 7 2 4
Output 3
-1