ZZ-function, a shorter name of ZeedZaad-function is defines as followed.

Given 4 integers a, b, c and d your task is to find ZZ(c, d).

Input

First line is a number of test cases t (t ≤ 200).

Each test case is a line containing 4 integers a, b, c and d (0 ≤ a, b ≤ 109, 1 ≤ c ≤ 100, 1 ≤ c * d ≤ 108).

Output

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