using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, a[NMAX];
bool visited[NMAX];
void solve(void)
{
    vi ans(n + 1, NMAX);
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != a[i - 1])
        {
            ans[i] = a[i - 1];
            visited[ans[i]] = true;
        }
    }
    visited[a[n]] = true;
    int p = 0;
    for (int i = 1; i <= n; ++i)
    {
        while (visited[p])
            ++p;
        if (ans[i] == NMAX)
        {
            ans[i] = p;
            visited[p] = true;
        }
        cout << ans[i] << " ";
    }
}
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    solve();
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, a[NMAX];
bool increasing[NMAX];
void solve(void)
{
    vi ans;
    ans.push_back(a[0]);
    for (int i = 1; i <= n; ++i)
    {
        if (increasing[i] != increasing[i - 1])
            ans.push_back(a[i - 1]);
    }
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            if (i > 0)
                increasing[i] = (a[i] >= a[i - 1]);
        }
        increasing[0] = increasing[1];
        increasing[n] = !increasing[n - 1];
        solve();
    }
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e5 + 11;
int n, x, a[NMAX];
int solve(void)
{
    int l, r;
    if (accumulate(a, a + n, (ll)0) % x != 0)
        return n;
    l = 0;
    while (l < n and (a[l] % x == 0))
        ++l;
    r = n - 1;
    while (r >= 0 and (a[r] % x == 0))
        --r;
    if (l == n or r == -1)
        return -1;
    return n - min(l + 1, n - r);
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> x;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int solve(string s)
{
    int n = s.size();
    vi acc(n, 0);
    for (int i = 0; i < n; ++i)
    {
        acc[i] = (s[i] == '1');
        if (i != 0)
            acc[i] += acc[i - 1];
    }
    auto ones = [=](int l, int r) -> int {
        int ans = acc[r];
        if (l != 0)
            ans -= acc[l - 1];
        return ans;
    };
    auto zeros = [=](int l, int r) -> int {
        int ans = (r - l + 1) - ones(l, r);
        return ans;
    };
    int ans = INT_MAX;
    ans = min(ans, acc[n - 1]);
    ans = min(ans, n - acc[n - 1]);
    for (int i = 0; i < n - 1; ++i)
    {
        ans = min(ans, ones(0, i) + zeros(i + 1, n - 1));
        ans = min(ans, zeros(0, i) + ones(i + 1, n - 1));
    }
    return ans;
}
int main(void)
{
    int t;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> s;
        cout << solve(s) << endl;
    }
    return 0;
}

using namespace std;
bool solve(int x, int evens, int odds)
{
    if (odds == 0)
        return false;
    if (odds % 2 == 0)
        odds -= 1;
    int xp = x - 1;
    odds -= 1;
    xp -= min(odds, 2 * (xp / 2));
    return (xp - evens <= 0);
}
int main(void)
{
    int t, n, x, ai;
    cin >> t;
    while (t--)
    {
        cin >> n >> x;
        int rem[2] = {0, 0};
        for (int i = 0; i < n; ++i)
        {
            cin >> ai;
            rem[ai % 2]++;
        }
        cout << (solve(x, rem[0], rem[1]) ? "Yes" : "No") << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 5e5 + 11;
int n, m, topic[NMAX];
vi g[NMAX], blogs;
vi solve(void)
{
    auto cmp = [](int x, int y) { return topic[x] < topic[y]; };
    sort(blogs.begin(), blogs.end(), cmp);
    for (auto b : blogs)
    {
        sort(g[b].begin(), g[b].end(), cmp);
        int nxt = 1;
        for (auto v : g[b])
            if (nxt == topic[v])
                ++nxt;
        if (topic[b] != nxt)
            return {-1};
    }
    return blogs;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int u, v;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> topic[i];
        blogs.push_back(i);
    }
    for (auto u : solve())
        cout << u << " ";
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
int main(void)
{
    int t;
    ll n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        ll ans = 0;
        ll rate = 1;
        for (int i = 0; i < 64; ++i)
        {
            ans += max((ll)0, (ll)((n + 1 + rate - 1) / rate) - 1);
            rate *= 2;
        }
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 1024 + 11;
int n, s[NMAX];
int solve(void)
{
    sort(s, s + n);
    for (int k = 1; k < NMAX; ++k)
    {
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (binary_search(s, s + n, s[i] ^ k))
                ++cnt;
        if (cnt == n)
            return k;
    }
    return -1;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> s[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 10;
int n, m, diff[NMAX];
string a[NMAX], ans;
bool backtrack(int i)
{
    if (i == m)
        return true;
    vector<bool> visited(26, false);
    for (int j = 0; j < n; ++j)
    {
        char c = a[j][i];
        bool ok = true;
        if (visited[c - 'a'])
            continue;
        visited[c - 'a'] = true;
        for (int k = 0; k < n; ++k)
        {
            diff[k] += (a[j][i] != a[k][i]);
            if (diff[k] > 1)
                ok = false;
        }
        ans[i] = c;
        if (ok and backtrack(i + 1))
            return true;
        ans[i] = ' ';
        for (int k = 0; k < n; ++k)
            diff[k] -= (a[j][i] != a[k][i]);
    }
    return false;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        ans.resize(m, ' ');
        fill(diff, diff + NMAX, 0);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        if (backtrack(0))
            cout << ans << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 50;
int n;
bool bomb[NMAX][NMAX];
bool valid(int i, int j)
{
    if (i == n - 1 or j == n - 1)
        return true;
    return bomb[i + 1][j] or bomb[i][j + 1];
}
bool board_possible(void)
{
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = n - 1; j >= 0; --j)
        {
            if (bomb[i][j] and not valid(i, j))
                return false;
        }
    }
    return true;
}
int main(void)
{
    char c;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cin >> c;
                bomb[i][j] = c == '1';
            }
        }
        cout << (board_possible() ? "YES" : "NO") << endl;
    }
    return 0;
}