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) = \begin{cases} 1 & \text{nếu } n = 1 \\ 1 & \text{nếu } n = 2 \\ Fibonacci(n-1) + Fibonacci(n-2) & \text{nếu } n > 2 \end{cases}$$

Xét hàm ~f(x, y)~ sau: $$f(x, y) = \begin{cases} y & \text{nếu } x = 0 \\ x & \text{nếu } y = 0 \\ \alpha \times f(x-1, y) + \beta \times f(x, y-1) + g(x, y) & \text{nếu } x \neq 0 \text{ và } y \neq 0 \end{cases}$$ 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) \pmod 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

• 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.

Sample Input 1

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

Sample Output 1

10
10
3

Subtasks

• Subtask 1 (20 điểm): ~x, y \le 10; \alpha, \beta, B \le 10^6~.
• Subtask 2 (20 điểm): ~x, y \le 50; \alpha, \beta, B \le 10^9~.
• Subtask 3 (15 điểm): ~x, y \le 50; \alpha, \beta, B \le 10^{18}~.
• Subtask 4 (15 điểm): ~x, y \le 500; \alpha, \beta, B \le 10^{18}~.