Chị em Liên và An là hai đứa trẻ được mẹ giao trông coi một cửa hàng tạp hoá nhỏ xíu tại một phố huyện nghèo bên cạnh ga xe lửa, để giúp gia đình vốn đã lao đao: cha mất việc, cả nhà phải bỏ Hà Nội chuyển về sinh sống ở quê. Cũng như nhiều người dân lam lũ tại phố huyện, hai chị em Liên, An vừa bán hàng vừa trông chờ chuyến tàu đêm từ Hà Nội về, ầm ầm lăn bánh qua phố huyện rồi khuất dạng, im tiếng trong trời đêm sâu thẳm. Lúc đó người buôn bán ở phố huyện mới dọn hàng sau một tối ế ẩm để trở về nhà. Còn hai đứa trẻ dần dần chìm vào giấc ngủ yên tĩnh.

Sáng hôm sau đúng \(3h\) sáng chị em Liên và An thức dậy, vẫn trông coi cửa hàng tạp hóa như bình thường thì có một quý ông vào mua thuốc lá. Quý ông này là một người quý tộc và không ai khác đó chính là algorit. Sau khi quý ông mua xong bao thuốc lá, ông này đã đặt câu đố cho chị em Liên và An, quý ông này cho Liên một số nguyên dương \(A\) và An một số nguyên dương \(B\). Liên và An lấy hai số đó cộng lại với nhau thì được số mới, số mới được đưa cho An và Liên sẽ nhận lấy số cũ của An số của Liên hiện tại. Việc đó được lặp đi lặp lại \(n\) lần hay có thể tổng quát nó như sau.

• \(f(1) = A\)
• \(f(2) = B\)
• \(f(n) = (f(n - 1) + f(n - 2))\) \(mod\) \(C\)

Yêu cầu của quý ông này là sau khi sắp xếp lại các giá trị của \(f(1),f(2),f(3),...,f(n)\) theo thứ tự tăng dần thì số thứ \(k(k \le n)\) mang giá trị là bao nhiêu. Quý ông này sẽ thưởng cho hai chị em một bao thuốc lá nếu trả lời đúng. Hãy giúp chị em Liên và An giải bài toán trên nhé.

Input

• Dòng đầu tiên gồm một số nguyên dương \(T(T \le 10)\) là số lượng câu hỏi.
• Mỗi câu hỏi tương ứng với \(5\) số nguyên dương \(n,C,k,A,B(A,B \le 10^{18})\).

Output

• Gồm \(T\) dòng, mỗi dòng là đáp án của câu hỏi tương ứng theo thứ tự.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,C \le 10^5\).*
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^{18},C \le 10^5\).*

Example

1
8 15 7 1 1 

8