Cho 3 số N, A, P, xây dựng danh sách N phần tử như sau

array[0] = (A*A) % P

array[i] = (array[i-1]*A) % P với 0 < i < N

Tìm phần tử nhỏ thứ K trong danh sách

Input

• Dòng đầu tiên là số test cases T (1 ≤ T ≤ 10)

• Mỗi dòng tiếp theo mô tả một test case, gồm 4 số nguyên N (1 ≤ N ≤ ~2*10^{7}~), A (1 ≤ A ≤ ~10^{9}~), P là số nguyên tố lớn hơn ~10^{9}~, và K (1 ≤ K ≤ N)

Output

• In ra phần tử nhỏ thứ K trong danh sách

Sample Input:

2
70 1356 1000000297 1
63 159 1000002937 3

Sample Output:

1838736
13341658