#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int x[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, k, t;

    cin >> t;

    while (t--) {

        cin >> n >> k;

        int ans = ;

        for (int i = ; i < k; i++) cin >> x[i];

        ans = max(ans, x[]);

        ans = max(ans, n - x[k - ] + );

        for (int i = ; i < k; i++) ans = max(ans, (x[i] - x[i - ] + ) / );

        cout << ans << endl;

    }

    return ;

}

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int l[], r[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, t;

    cin >> t;

    while (t--) {

        cin >> n;

        for (int i = ; i < n; i++) cin >> l[i] >> r[i];

        int time = ;

        for (int i = ; i < n; i++) {

            if (time < l[i]) time = l[i];

            if (time > r[i]) {

                cout <<  << ' ';

                continue;

            }

            cout << time << ' ';

            time++;

        }

        cout << endl;

    }

    return ;

}

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int a[], p[], b[];

bool f[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n;

    cin >> n;

    for (int i = ; i <= n; i++) {

        cin >> a[i];

        p[a[i]] = i;

    }

    char ch;

    for (int i = ; i < n; i++) {

        cin >> ch;

        b[i] = ch - '';

    }

    b[n] = ;

    bool ok = true;

    int ptr = ;

    while (ptr <= n) {

        if (b[ptr] == ) {

            if (a[ptr] != ptr) ok = false;

            ptr++;

        } else {

            int l = ptr;

            while (b[ptr] == ) ptr++;

            int r = ptr;

            for (int i = l; i <= r; i++) f[i] = false;

            for (int i = l; i <= r; i++) f[a[i]] = true;

            for (int i = l; i <= r; i++) if (!f[i]) ok = false;

            ptr++;

        }

    }

    if (ok) cout << "YES" << endl;

    else cout << "NO" << endl;

    return ;

}