Tính: \(a^{b^c}\) \(mod\) \(10^{18} + 9\).

Input

• Dòng đầu ghi \(Q\) không quá \(5000\) - số câu hỏi.
• \(Q\) dòng tiếp theo mỗi dòng ghi 3 số \(a,b,c\) không quá \(10^{15}\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

3
2 3 2
5 2 2
3 4 5

512
625
824168097938645257