TopCoder

Caido
主唱太拼命了

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

71.4% (5/7)

Tags

Description

祺祺在上幼稚園的時候在學排列組合,他的老師說:

對於兩個數字 nk,若 0kn,則 (nk)=n!k!(nk)! 代表「有 n 個相異的東西,從中選取 k 個的方法數」。老師也說這些 (nk) 會一下子就跑到很大!舉例來說,(202)=190,但是 (2010) 就會飛到 184756 了!

陷入了沈思的祺祺馬上就想到了一個問題:有幾個 n,k 滿足 0kn,且 (nk)lr 之間呢?因為他發現對於任何的 x,皆有 (x0)=1,所以他還多加了一個限制 N,表示 n 一定不能大於 N,否則沒完沒了。此外,在一筆測試資料中,你還需要解決 T 筆像是這樣的詢問。

請寫一支程式幫忙祺祺解決這個問題吧!

Input Format

輸入的第一行有一個整數 T,代表詢問數量。

接下來 T 行每一行有三個整數 l,r,N

  • 1T104
  • 1lr1012
  • 1N1000

Output Format

請輸出 T 個數字,代表有幾個 (n,k) 滿足題目的條件。

Sample Input 1

1
2 3 7

Sample Output 1

3

Sample Input 2

5
4 10 23
10 20 19
9 18 34
16 17 20
12 14 27

Sample Output 2

17
25
24
4
6

Hints

Problem Source

IOICamp 2022 Day5 pB

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~4 N44 6
3 5~8 T=1 18
4 9~12 r104 27
5 0~15 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2 5
1 2000 262144 65536 1 2 5
2 2000 262144 65536 2 5
3 2000 262144 65536 2 5
4 2000 262144 65536 2 5
5 2000 262144 65536 3 5
6 2000 262144 65536 3 5
7 2000 262144 65536 3 5
8 2000 262144 65536 3 5
9 2000 262144 65536 4 5
10 2000 262144 65536 4 5
11 2000 262144 65536 4 5
12 2000 262144 65536 4 5
13 2000 262144 65536 5
14 2000 262144 65536 5
15 2000 262144 65536 5