"Shuvo Noboborsho" is the traditional greeting for Bengalis in the Bengali new year which means "Happy New Year". Here “Noboborsho” means “New Year”. And "Baishakhi Mela" is the traditional cultural fair held on the occasion of Bengali new year.

This year, Pranto has got $N$ panjabis and $M$ pajamas as gifts of Noboborsho from his parents and relatives. He decided to visit the Baishakhi Mela with his two best friends, Auditi and Sanonda wearing a panjabi and a pajama. But he became confused of which one he should wear. So, he got an idea of wearing a panjabi along with a pajama in all possible ways and told Auditi and Sanonda to choose the best combination. It needs $S$ seconds to put on a panjabi along with a pajama. They will leave for the Baishakhi Mela after $K$ seconds. Now, Pranto asked Auditi how many unique combinations of a panjabi and a pajama he can try within this period of time. And Pranto also promised Auditi to buy her a nice gift from the Baishakhi Mela if she can answer his question instantly.

Now, Auditi needs help from a programmer like you to calculate the answer instantly. Can you help her?

Input

The first line of the input contains an integer $T ( 1 \le T \le 10^5 )$$-$ the number of test cases.

Then each of $T$ test cases contain a line of four space separated integers $N$, $M$, $S$, $K$$( 1 \le N, M, S \le 10^6,$$1 \le K \le 10^9 )$ the number of panjabis, the number of pajamas, required time for putting on a panjabi along with a pajama and the total time they have before leaving respectively.

Output

Output contains $T$ lines. The $i^{th}$$( 1 \le i \le T )$ line contains an integer $C-$ the number of unique combinations of a panjabi along with a pajama Pranto can try for the $i^{th}$ test case.