| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 16 | 6 | 6 | 37.500% |
Кецилий украл жезл Ватумба, и теперь Доктор Стрэндж преследует его по разным альтернативным реальностям. Буквально только что Доктор потерял его, но благодаря своим способностям он все еще может следить, где Кецилий сейчас находится.
Стрэндж записал все номера реальностей, в которых успел побывать Кецилий, и решил найти какую-нибудь закономерность его действий. Однако внезапно Доктор понял, что все номера он записал подряд без пропусков, и теперь невозможно точно восстановить номера реальностей.
Тем не менее Стивен запомнил три важных условия:
Точно восстановить передвижения злодея невозможно, поэтому сейчас Стрэндж хочет хотя бы знать количество способов разбить получившееся число на $k$ других, чтобы выполнялись условия, описанные выше.
В первой строке содержится число $t$ --- количество тестов (1ドル \le t \le 100$). В $i$-й из следующих $t$ строк содержится описание $i$-го теста.
Тест описывается четырьмя числами $x,ドル $l,ドル $r,ドル $k$ --- числом, полученным Доктором Стрэнджем, границами для абсолютной разницы и количеством реальностей, в которых побывал Кецилий (1ドル \le x \le 10^{18}, 0 \le l \le r \le 10^{18}, 1 \le k \le 18$).
На каждый тест в отдельной строке выведите ответ на него --- искомое количество разбиений.
3 248 16 45 2 248 16 46 2 4444 1 5 2
1 2 0
В первом тесте возможно только одно разбиение, удовлетворяющее ограничениям на абсолютную разность: сначала Кецилий мог быть в реальности номер 24ドル,ドル а потом в реальности номер 8ドル$.
Во втором тесте возможны два разбиения: 2ドル \rightarrow 48,ドル 24ドル \rightarrow 8$.