Beo vừa tìm thấy một danh sách các số nguyên ~NUMS~ được sắp xếp tăng dần (các phần tử đều khác nhau). Tuy nhiên, TanTan – vì nghịch ngợm – đã xoay mảng này tại một vị trí bí mật (gọi là chỉ số ~K~, với ~(1 ≤ K < NUMS.length)~.

Mảng sau khi bị xoay sẽ có dạng: ~[NUMS_{k}, NUMS_{k+1}, ..., NUMS_{n-1}, NUMS_0, ..., NUMS_{K-1}]~

Ví dụ: nếu ~NUMS = [1,2,3,4,5,6,7]~ và K=3 (xoay tại vị trí 3), mảng mới sẽ là ~[4,5,6,7,1,2,3]~.

Giờ đây, Cheow muốn tìm một số nguyên ~X~ trong mảng ~NUMS~ đã bị xoay. Hãy giúp Cheow viết một thuật toán có độ phức tạp O(logN) để trả về chỉ số của ~X~ nếu nó xuất hiện, hoặc trả về ~-1~ nếu không tồn tại.

Input

• Dòng đầu tiên chứa số nguyên ~T~ là số lượng test ~(1 ≤ T ≤ 100)~.

• Với mỗi test:

  • Một dòng chứa hai số nguyên ~N~ và ~X~ ~(1 ≤ N ≤ 10^5, |X| ≤ 10^9)~.
  • Một dòng tiếp theo chứa ~N~ số nguyên ~A_0, A_1, ..., A_{N-1}~ ~( |A_i| ≤ 10^9 )~ – là mảng đã bị xoay.

Tổng ~N~ của tất cả các test không vượt quá ~10^7~.

Output

• Với mỗi test, in ra một dòng là chỉ số của ~X~ trong mảng nếu tồn tại, hoặc ~-1~ nếu không có.

📌 Example

Input

3
7 0
5 6 7 0 1 2 3
7 4
5 6 7 0 1 2 3
1 5
10

Output

3
-1
-1