Problem: It is only a few days until Seollal (Korean Lunar New Year), and Jaehyun has invited his family to his garden. There are kids among the guests. To make the gathering more fun for the kids, Jaehyun is going to run a game of hide-and-seek.

The garden can be represented by a n × m grid of unit cells. Some (possibly zero) cells are blocked by rocks, and the remaining cells are free. Two cells are neighbors if they share an edge. Each cell has up to 4 neighbors: two in the horizontal direction and two in the vertical direction. 

Since the garden is represented as a grid, we can classify the cells in the garden as either "black" or "white". The top-left cell is black, and two cells which are neighbors must be different colors. Cell indices are 1-based, so the top-left corner of the garden is cell (1, 1).

Jaehyun wants to turn his garden into a maze by placing some walls between two cells. Walls can only be placed between neighboring cells. If the wall is placed between two neighboring cells a and b, then the two cells a and b are not neighboring from that point. One can walk directly between two neighboring cells if and only if there is no wall directly between them. 

A maze must have the following property. For each pair of free cells in the maze, there must be exactly one simple path between them. A simple path between cells a and b is a sequence of free cells in which the first cell is a, the last cell is b, all cells are distinct, and any two consecutive cells are neighbors which are not directly blocked by a wall.

At first, kids will gather in cell (1, 1), and start the hide-and-seek game. A kid can hide in a cell if and only if that cell is free, it is not (1, 1), and has exactly one free neighbor. Jaehyun planted roses in the black cells, so it's dangerous if the kids hide there. So Jaehyun wants to create a maze where the kids can only hide in white cells.

You are given the map of the garden as input. Your task is to help Jaehyun create a maze.

Input

Your program will be judged in multiple test cases.

The first line contains the number of test cases t. (1 ≤ t ≤ 100). Afterward, t test cases with the described format will be given.

The first line of a test contains two integers n, m (2 ≤ n, m ≤ 20), the size of the grid.

In the next n line of a test contains a string of length m, consisting of the following characters (without any whitespace): 

  * O: A free cell. 
  * X: A rock. 



It is guaranteed that the first cell (cell (1, 1)) is free, and every free cell is reachable from (1, 1). 

If t ≥ 2 is satisfied, then the size of the grid will satisfy n ≤ 10, m ≤ 10. In other words, if any grid with size n > 10 or m > 10 is given as an input, then it will be the only input on the test case (t = 1).

Output

For each test case, print the following:

If there are no possible mazes, print a single line NO.

Otherwise, print a single line YES, followed by a grid of size (2n-1) × (2m-1) denoting the found maze. The rules for displaying the maze follows. All cells are indexed in 1-base.

  * For all 1 ≤ i ≤ n, 1 ≤ j ≤ m, if the cell (i, j) is free cell, print 'O' in the cell (2i-1, 2j-1). Otherwise, print 'X' in the cell (2i-1, 2j-1). 
  * For all 1 ≤ i ≤ n, 1 ≤ j ≤ m-1, if the neighboring cell (i, j), (i, j+1) have wall blocking it, print ' ' in the cell (2i-1, 2j). Otherwise, print any printable character except spaces in the cell (2i-1, 2j). A printable character has an ASCII code in range [32, 126]: This includes spaces and alphanumeric characters. 
  * For all 1 ≤ i ≤ n-1, 1 ≤ j ≤ m, if the neighboring cell (i, j), (i+1, j) have wall blocking it, print ' ' in the cell (2i, 2j-1). Otherwise, print any printable character except spaces in the cell (2i, 2j-1) 
  * For all 1 ≤ i ≤ n-1, 1 ≤ j ≤ m-1, print any printable character in the cell (2i, 2j). 



Please, be careful about trailing newline characters or spaces. Each row of the grid should contain exactly 2m-1 characters, and rows should be separated by a newline character. Trailing spaces must not be omitted in a row.

Example

Input


4
2 2
OO
OO
3 3
OOO
XOO
OOO
4 4
OOOX
XOOX
OOXO
OOOO
5 6
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO


Output


YES
OOO
  O
OOO
NO
YES
OOOOO X
  O O  
X O O X
  O    
OOO X O
O O   O
O OOOOO
YES
OOOOOOOOOOO
  O   O   O
OOO OOO OOO
O   O   O  
OOO OOO OOO
  O   O   O
OOO OOO OOO
O   O   O  
OOO OOO OOO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<int, int>;
using vi = vc<int>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <int i, class T>
void print_tuple(ostream&, const T&) {}
template <int i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, int suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(int n, int off = 0) {
  vi v(n);
  for (int i = int(0); i < int(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = int(0); i < int(v.size()); i++)
    print(v[i], i == int(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "YES"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "NO"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "POSSIBLE"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "IMPOSSIBLE"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
int botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
int mask(int i) { return (int(1) << i) - 1; }
bool inc(int first, int second, int c) {
  return first <= second && second <= c;
}
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static random_device rd;
  static mt19937_64 gen(rd());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
int lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
template <class LM, class RM>
struct MatroidIntersection {
  int n, m, s;
  LM& lm;
  RM& rm;
  struct Edge {
    int to, cost, id;
    friend ostream& operator<<(ostream& os, const Edge& e) {
      return os << "{T:" << e.to << ", C:" << e.cost << ", I:" << e.id << "}";
    }
  };
  vc<tuple<int, int, int>> es;
  vvc<Edge> g;
  MatroidIntersection(LM& llm, RM& rrm) : lm(llm), rm(rrm) {
    n = lm.size();
    m = rm.size();
    s = n + m;
  }
  void AddEdge(int first, int second, int c) {
    assert(0 <= first && first < n);
    assert(0 <= second && second < m);
    assert(0 <= c);
    es.emplace_back(first, second, c);
  }
  vi h;
  vc<pi> dist, prev;
  void FindShortest(const vi& src) {
    dist.assign(s, pi(inf, -1));
    prev.assign(s, pi(-1, -1));
    using Node = tuple<int, int, int>;
    queue<Node> pq;
    const auto Reach = [&](int v, int d, int step, int j, int k) {
      if (pi(d, step) < dist[v]) {
        dist[v] = pi(d, step);
        prev[v] = pi(j, k);
        pq.push(make_tuple(d, step, v));
      }
    };
    for (auto i : src) Reach(i, 0, 0, -1, -1);
    while (!pq.empty()) {
      int d, step, v;
      tie(d, step, v) = pq.front();
      pq.pop();
      if (dist[v] != pi(d, step)) continue;
      for (auto e : g[v]) {
        assert(e.cost + h[v] - h[e.to] >= 0);
        Reach(e.to, d + e.cost + h[v] - h[e.to], step + 1, v, e.id);
      }
    }
  }
  int Augment(vc<bool>& use) {
    g.assign(s, vc<Edge>());
    vi m1, m2;
    for (int i = int(0); i < int(es.size()); i++) {
      int first, second, c;
      tie(first, second, c) = es[i];
      if (use[i]) {
        g[n + second].push_back(Edge{first, -c, i});
        m1.push_back(first);
        m2.push_back(second);
      } else {
        g[first].push_back(Edge{n + second, c, i});
      }
    }
    vi src, dst;
    {
      auto w = lm.Get(m1);
      src = w.first;
      if (src.empty()) return -1;
      for (auto e : w.second) g[e.first].push_back(Edge{e.second, 0, -1});
    }
    {
      auto w = rm.Get(m2);
      dst = w.first;
      if (dst.empty()) return -1;
      for (auto e : w.second)
        g[n + e.second].push_back(Edge{n + e.first, 0, -1});
    }
    FindShortest(src);
    pair<pi, int> w(pi(inf / 2, -1), -1);
    for (auto i : dst) chmin(w, make_pair(dist[n + i], n + i));
    if (w.second == -1) return -1;
    int x = w.second;
    while (prev[x].first != -1) {
      int i = prev[x].second;
      if (i != -1) use[i] = !use[i];
      x = prev[x].first;
    }
    int mn = w.first.first;
    for (int i = int(0); i < int(s); i++) {
      h[i] += min(dist[i].first, mn);
      chmin(h[i], inf);
    }
    return h[w.second];
  }
  pair<int, vi> Solve() {
    h.assign(s, 0);
    vc<bool> use(es.size());
    int c = 0, f;
    while ((f = Augment(use)) >= 0) c += f;
    vi sol;
    for (int i = int(0); i < int(es.size()); i++)
      if (use[i]) sol.push_back(i);
    return make_pair(c, sol);
  }
};
struct UnionFind {
  vi rank, par;
  void Init(int n) {
    rank.assign(n, 0);
    par.assign(n, -1);
  }
  int Find(int i) { return par[i] == -1 ? i : (par[i] = Find(par[i])); }
  bool Same(int first, int second) { return Find(first) == Find(second); }
  bool Unite(int first, int second) {
    first = Find(first);
    second = Find(second);
    if (first == second) return false;
    if (rank[first] < rank[second]) swap(first, second);
    par[second] = first;
    if (rank[first] == rank[second]) rank[first]++;
    return true;
  }
};
struct MST {
  int n;
  vector<pi> es;
  MST(int nn) { n = nn; }
  void AddEdge(int first, int second) {
    assert(0 <= first && first < n);
    assert(0 <= second && second < n);
    es.emplace_back(first, second);
  }
  int size() { return es.size(); }
  UnionFind uf;
  pair<vi, vc<pi>> Get(const vi& cur) {
    uf.Init(n);
    vi t(size(), 0);
    for (auto i : cur) {
      uf.Unite(es[i].first, es[i].second);
      t[i] = 1;
    }
    vi src;
    for (int i = int(0); i < int(size()); i++)
      if (!t[i]) {
        if (!uf.Same(es[i].first, es[i].second)) {
          src.push_back(i);
          t[i] = 2;
        }
      }
    vc<pi> res;
    for (int i = int(0); i < int(size()); i++)
      if (t[i] == 1) {
        uf.Init(n);
        for (int j = int(0); j < int(size()); j++)
          if (t[j] == 1 && j != i) uf.Unite(es[j].first, es[j].second);
        for (int j = int(0); j < int(size()); j++)
          if (!t[j])
            if (!uf.Same(es[j].first, es[j].second)) res.emplace_back(i, j);
      }
    return make_pair(src, res);
  }
};
struct Matroid2 {
  vi g, mx;
  int n;
  int s;
  Matroid2(vi gg, vi mm) : g(gg), mx(mm), n(g.size()), s(mx.size()) {}
  int size() { return n; }
  pair<vi, vc<pi>> Get(const vi& cur) {
    vi cnt(s), used(n);
    vc<array<int, 2>> waf(s);
    for (auto i : cur) {
      used[i] = 1;
      if (g[i] != -1) {
        waf[g[i]][cnt[g[i]]++] = i;
      }
    }
    vi src;
    for (int i = int(0); i < int(n); i++)
      if (!used[i] && (g[i] == -1 || cnt[g[i]] < mx[g[i]])) src.push_back(i);
    vc<pi> res;
    for (int i = int(0); i < int(n); i++)
      if (!used[i] && g[i] != -1 && cnt[g[i]] == mx[g[i]])
        for (int j = int(0); j < int(cnt[g[i]]); j++)
          res.emplace_back(waf[g[i]][j], i);
    return make_pair(src, res);
  }
};
void slv() {
  int n, m;
  cin >> n >> m;
  vc<string> z(n);
  for (int i = int(0); i < int(n); i++) cin >> z[i];
  vvc<int> acth(n + 1, vi(m)), actv(n, vi(m + 1));
  vvc<int> blh(n + 1, vi(m, -1)), blv(n, vi(m + 1, -1));
  int bs = 0;
  for (int i = int(0); i < int(n); i++)
    for (int j = int(0); j < int(m); j++)
      if (z[i][j] == 'O') {
        acth[i][j] += 1;
        acth[i + 1][j] += 1;
        actv[i][j] += 1;
        actv[i][j + 1] += 1;
        if ((i || j) && (i + j) % 2 == 0) {
          blh[i][j] = bs;
          blh[i + 1][j] = bs;
          blv[i][j] = bs;
          blv[i][j + 1] = bs;
          bs++;
        }
      }
  UnionFind uf;
  uf.Init((n + 1) * (m + 1));
  vc<int> idbuf((n + 1) * (m + 1), -1);
  int s = 0;
  auto getid = [&](int i, int j) {
    int k = uf.Find(i * (m + 1) + j);
    if (idbuf[k] == -1) idbuf[k] = s++;
    return idbuf[k];
  };
  for (int i = int(0); i < int(n + 1); i++)
    for (int j = int(0); j < int(m); j++)
      if (acth[i][j] == 1) {
        uf.Unite(i * (m + 1) + j, i * (m + 1) + j + 1);
      }
  for (int i = int(0); i < int(n); i++)
    for (int j = int(0); j < int(m + 1); j++)
      if (actv[i][j] == 1) {
        uf.Unite(i * (m + 1) + j, (i + 1) * (m + 1) + j);
      }
  for (int i = int(0); i < int(n + 1); i++)
    for (int j = int(0); j < int(m); j++)
      if (acth[i][j]) {
        getid(i, j);
        getid(i, j + 1);
      }
  for (int i = int(0); i < int(n); i++)
    for (int j = int(0); j < int(m + 1); j++)
      if (actv[i][j]) {
        getid(i, j);
        getid(i + 1, j);
      }
  MST mst(s);
  vc<tuple<int, int, int>> einfo;
  vi bidx;
  for (int i = int(0); i < int(n + 1); i++)
    for (int j = int(0); j < int(m); j++)
      if (acth[i][j] == 2) {
        mst.AddEdge(getid(i, j), getid(i, j + 1));
        bidx.push_back(blh[i][j]);
        einfo.emplace_back(0, i, j);
      }
  for (int i = int(0); i < int(n); i++)
    for (int j = int(0); j < int(m + 1); j++)
      if (actv[i][j] == 2) {
        mst.AddEdge(getid(i, j), getid(i + 1, j));
        bidx.push_back(blv[i][j]);
        einfo.emplace_back(1, i, j);
      }
  vi mx(bs, 2);
  for (int i = int(0); i < int(n + 1); i++)
    for (int j = int(0); j < int(m); j++)
      if (acth[i][j] == 1 && blh[i][j] != -1) {
        mx[blh[i][j]]--;
      }
  for (int i = int(0); i < int(n); i++)
    for (int j = int(0); j < int(m + 1); j++)
      if (actv[i][j] == 1 && blv[i][j] != -1) {
        mx[blv[i][j]]--;
      }
  if (mx.size() && *min_element(mx.begin(), mx.end()) < 0) {
    cerr << "No Answer" << endl;
    no(0);
    return;
  }
  Matroid2 m2(bidx, mx);
  MatroidIntersection<MST, Matroid2> mi(mst, m2);
  for (int i = int(0); i < int(bidx.size()); i++) mi.AddEdge(i, i, 0);
  auto ans = mi.Solve().second;
  if ((int)ans.size() == s - 1) {
    cerr << "Found an Answer" << endl;
    yes(0);
    vc<string> x(n * 2 - 1, string(m * 2 - 1, '#'));
    for (int i = int(0); i < int(n); i++)
      for (int j = int(0); j < int(m); j++) x[i * 2][j * 2] = z[i][j];
    for (int i = int(0); i < int(n - 1); i++)
      for (int j = int(0); j < int(m - 1); j++) x[i * 2 + 1][j * 2 + 1] = '.';
    auto useedge = [&](tuple<int, int, int> e) {
      int t, i, j;
      tie(t, i, j) = e;
      if (t == 0) {
        if (i == 0 || i == n) return;
        x[i * 2 - 1][j * 2] = ' ';
      } else {
        if (j == 0 || j == m) return;
        x[i * 2][j * 2 - 1] = ' ';
      }
    };
    for (auto e : ans) {
      useedge(einfo[e]);
    }
    for (int i = int(0); i < int(n + 1); i++)
      for (int j = int(0); j < int(m); j++)
        if (acth[i][j] == 1) {
          useedge(make_tuple(0, i, j));
        }
    for (int i = int(0); i < int(n); i++)
      for (int j = int(0); j < int(m + 1); j++)
        if (actv[i][j] == 1) {
          useedge(make_tuple(1, i, j));
        }
    for (int i = int(0); i < int(n - 1); i++)
      for (int j = int(0); j < int(m); j++)
        if (z[i][j] == 'X' && z[i + 1][j] == 'X') x[i * 2 + 1][j * 2] = ' ';
    for (int i = int(0); i < int(n); i++)
      for (int j = int(0); j < int(m - 1); j++)
        if (z[i][j] == 'X' && z[i][j + 1] == 'X') x[i * 2][j * 2 + 1] = ' ';
    for (auto v : x) cout << v << endl;
  } else {
    cerr << "No Answer" << endl;
    no(0);
  }
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  int t;
  cin >> t;
  for (int _ = int(0); _ < int(t); _++) slv();
}