C. 琪露诺放冰块
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

琪露诺有一个长为 $$$n$$$，宽为 $$$m$$$ 的长方体$$$^*$$$冰箱和若干个长为 $$$a$$$，宽为 $$$b$$$ 的长方体冰块，冰箱与冰块高度一样，她想知道在不能旋转的情况下她最多能把多少冰块放入冰箱。由于琪露诺是一个 baka，所以她把这个问题交给了你。

$$$^*$$$长方体的边和水平同方向的叫做"长"，和前后同方向的叫做"宽"，和竖直同方向的叫做"高"。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 100)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含 4 个整数 $$$n,m,a,b\ (1 \le a \le n \le 10^4,1 \le b \le m \le 10^4)$$$，含义如题。

Output

对于每个测试用例，输出一行一个整数，表示答案。

Example
Input
3
3 3 2 1
3 3 2 2
10000 10000 1 1
Output
3
1
100000000
Note
第二个测试点的一种可行放法。