Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử ~1~ và ~1~, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci như sau:

• ~Fibonacci(n)~ ~= 1~ với ~n = 1~, ~2~
• ~Fibonacci(n)~ ~=~ ~Fibonacci(n - 1)~ ~+~ ~Fibonacci(n - 2)~

Xét hàm ~f(x~, ~y)~ sau:

• ~f(x~, ~y)~ ~= x~ nếu ~y = 0~
• ~f(x~, ~y)~ ~= y~ nếu ~x = 0~
• ~f(x, y) = \alpha \times f(x - 1, y) + \beta \times f(x, y - 1) + g(x, y)~ nếu ~x~, ~y > 0~.

Trong đó, ~g(x~, ~y)~ là ước số chung lớn nhất của ~Fibonacci(x)~ và ~Fibonacci(y)~.

Yêu cầu:

Cho ~4~ số nguyên không âm ~x~, ~y~, ~\alpha~, ~\beta~ và số nguyên dương ~B~, hãy tính hàm ~f(x~, ~y) \bmod B~.

Input

Dòng đầu tiên ghi số nguyên dương ~K~ là số lượng bộ dữ liệu.

Tiếp đến là ~K~ dòng, mỗi dòng chứa ~5~ số nguyên ~x~, ~y~, ~\alpha~, ~\beta~, ~B~ tương ứng với một bộ dữ liệu. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Kết quả: Ghi ra thiết bị ra chuẩn gồm ~K~ dòng, mỗi dòng ghi một số nguyên là giá trị hàm ~f~ tính được tương ứng với bộ dữ liệu trong file dữ liệu vào.

Giới hạn

• Subtask ~1~ (20/70 điểm): Giả thiết là ~x~, ~y \leq 10~; ~\alpha~, ~\beta~, ~B \leq 10^{6}~.
• Subtask ~2~ (20/70 điểm): Giả thiết là ~x~, ~y \leq 50~; ~\alpha~, ~\beta~, ~B \leq 10^{9}~.
• Subtask ~3~ (15/70 điểm): Giả thiết là ~x~, ~y \leq 50~; ~\alpha~, ~\beta~, ~B \leq 10^{18}~.
• Subtask ~4~ (15/70 điểm): Giả thiết là ~x~, ~y \leq 500~; ~\alpha~, ~\beta~, ~B \leq 10^{18}~.

Sample Input

3
0 10 1 1 100
10 0 1 1 100
1 1 1 1 100

Sample Output

10
10
3