추적

케실리우스가 와툼바의 지팡이를 훔쳐 닥터 스트레인지가 여러 대체 현실을 쫓고 있다. 방금 닥터가 그를 놓쳤지만, 자신의 능력 덕분에 케실리우스가 지금 어디에 있는지는 여전히 알 수 있다.

스트레인지는 케실리우스가 들렀던 현실의 번호를 모두 적었는데, 번호를 빈틈없이 한 줄로 이어 적어 버렸다. 그래서 원래 번호를 정확히 복원할 수 없게 되었다.

다만 스티븐은 다음 세 가지 조건을 기억하고 있다.

• 케실리우스는 정확히 $k$개의 현실에 들렀다.
• 각 현실의 번호는 0 이상의 정수이며, 앞에 0이 붙지 않는다(번호가 0인 현실은 예외다).
• 번호가 $x$인 현실에서 케실리우스는 항상 번호가 $y$인 현실로 이동했다. 이때 $x$와 $y$의 차의 절댓값은 $l$ 이상이고 $r$ 이하이다.

이동 경로를 정확히 알 수는 없으므로, 닥터는 이어 적은 숫자를 위 조건을 만족하는 $k$개의 수로 나누는 방법이 몇 가지인지 알고 싶어 한다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 100$). 다음 $t$개의 줄에는 각 테스트가 정수 네 개 $x$, $l$, $r$, $k$로 주어진다 ($1 \le x \le 10^{18}$, $0 \le l \le r \le 10^{18}$, $1 \le k \le 18$). 여기서 $x$는 스트레인지가 얻은 수이고, $l$과 $r$은 절댓값 차의 하한과 상한이며, $k$는 케실리우스가 들른 현실의 수이다.

각 테스트에 대해 조건을 만족하는 분할 방법의 수를 한 줄에 출력한다.

첫 번째 테스트에서는 절댓값 차 조건을 만족하는 분할이 하나뿐이다. 먼저 케실리우스는 번호 24인 현실에 있었고, 그다음 번호 8인 현실에 있었다. 두 번째 테스트에서는 가능한 분할이 두 가지이다: $2 \rightarrow 48$, $24 \rightarrow 8$.