ZZ

Input

First line is a number of test cases $t$ (t \leq 200).

Each test case is a line containing $4$ integers $a$, $b$, $c$ and $d$ (0 \leq a, b \leq 10^9, 1 \leq c \leq 100, 1 \leq c \cdot d \leq 10^8).

Output

For each test case print ZZ(c, d) mod $1000000009$.

Examples