Công ty Alpha giới thiệu siêu máy tính có khả năng thực hiện được một lượng tính toán rất lớn. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện tính giá trị sau: \((a^m)^{b^n}\), trong đó các số \(a, m, b, n\) là các số nguyên dương. Để kiểm tra kết quả do máy tính thực hiện, Hồng muốn xây dựng chương trình tính phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\).

Yêu cầu: Cho các bộ số nguyên dương \(a, m, b, n, K\), tính phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\).

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa số nguyên dương \(T (1 \leq T \leq 1000)\) là số bộ dữ liệu;
• Dòng thứ \(i (1 \leq i \leq T)\) trong \(T\) dòng tiếp theo chứa năm số nguyên dương \(a, m, b, n, K\).

Output

• Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, dòng thứ \(i (1\leq i \leq T)\) là phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\) tương ứng với bộ dữ liệu thứ trong dữ liệu vào.

Scoring

• Subtask #1 (\(20\%\) số điểm): \(a, m \leq 10; b = 1; n = 1; K \leq 10^5\);
• Subtask #2 (\(20\%\) số điểm): \(a, m \leq 10^6; b = 1; n = 1; K \leq 10^5\);
• Subtask #3 (\(20\%\) số điểm): \(a, m \leq 10^9; b = 1; n = 1; K \leq 10^5\);
• Subtask #4 (\(20\%\) số điểm): \(a, m \leq 10^9; b, n \leq 10^9; K \leq 10^5\);
• Subtask #5 (\(20\%\) số điểm): \(a, m \leq 10^9; b, n \leq 10^9; K \leq 10^7\);

Example

2
2 10 1 1 10
2 2 5 1 2000

4
1024