Shuvo Noboborsho!

Limits 1s, 256 MB

"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 NN panjabis and MM 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 SS seconds to put on a panjabi along with a pajama. They will leave for the Baishakhi Mela after KK 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(1T105)T ( 1 \le T \le 10^5 )- the number of test cases.

Then each of TT test cases contain a line of four space separated integers NN, MM, SS, KK(1N,M,S106,( 1 \le N, M, S \le 10^6,1K109) 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 TT lines. The ithi^{th}(1iT)( 1 \le i \le T ) line contains an integer CC- the number of unique combinations of a panjabi along with a pajama Pranto can try for the ithi^{th} test case.

Sample

InputOutput
4
3 9 1 27
5 7 2 30
10 9 5 1000
1000000 1000000 1000000 1000000000
27
15
90
1000