Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUMEDARRAY4 - Kth Smallest Element

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⁷), A (1 ≤ A ≤ 10⁹), P là số nguyên tố lớn hơn 10⁹, và K (1 ≤ K ≤ N)

Output

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

Example

Input:

70 1356 1000000297 1

63 159 1000002937 3

Output:

1838736

13341658

Submit solution!

Added by:	Ha Minh Ngoc
Date:	2016-05-21
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYPY3 PYTHON3 RUBY SQLITE SWIFT VB.NET