#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        string X;
        cin >> X;
        vector<int> A;
        bool begin = true;
        for (int i = X.size() - 1; i >=0; i--) {
            int cur = X[i] - '0';
            while (cur > 0) {
                int a = cur % 2;
                if (begin && a != 0) {
                    begin = false;
                } 
                if (!begin) A.push_back(a);
                cur /= 2;
            }
        }
        string C = "1";
        //只需要记录第一个元素以及翻转的次数就行了
        if (A.size() > 1) {
            for (int i = 1; i < A.size(); i++) {
                if (C[C.size() - 1] - '0' != A[i]) {
                    C += A[i] + '0';
                }
            }
        }
        cout << C << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int N,M;
        cin >> N >> M;
        vector<int> H;
        for (int i = 0; i < N; i++) {
            int temp;
            cin >> temp;
            H.push_back(temp);
        }
        //峰谷法，开始默认下降，结束默认上升
        bool rise = false;
        vector<int> topIdx, botIdx;
        for (int i = 0; i < N - 1; i++) {
            if (H[i] > H[i + 1]) {
                if (rise == true) {
                    rise = false;
                    //i为峰值
                    topIdx.push_back(i);
                }
            } else if (H[i] < H[i + 1]) {
                if (rise == false) {
                    rise = true;
                    //i为谷值
                    botIdx.push_back(i);
                }
            }
        }
        if (rise == false) botIdx.push_back(N - 1);
        int ret = botIdx.size() - 1;
        if (topIdx.size() > 1) {
            for (int i = 0; i < topIdx.size() - 1; i++) {
                if (topIdx[i] <= M - 1 && M - 1 <= topIdx[i + 1]) {
                    if (topIdx[i] == M - 1 || M - 1 == topIdx[i + 1]) {
                        ret--;
                        break;
                    }
                    if (H[topIdx[i]] == H[M - 1] || H[M - 1] == H[topIdx[i + 1]]) {
                        ret--;
                        break;
                    }
                }
            }
        }
        cout << max(0, ret) << endl;
    }
    return 0;
}