Casimir has a rectangular piece of paper with a checkered field of size n × m. Initially, all cells of the field are white.

Let us denote the cell with coordinates i vertically and j horizontally by (i, j). The upper left cell will be referred to as (1, 1) and the lower right cell as (n, m).

Casimir draws ticks of different sizes on the field. A tick of size d (d > 0) with its center in cell (i, j) is drawn as follows: 

  1. First, the center cell (i, j) is painted black. 
  2. Then exactly d cells on the top-left diagonally to the center and exactly d cells on the top-right diagonally to the center are also painted black. 
  3. That is all the cells with coordinates (i - h, j ± h) for all h between 0 and d are painted. In particular, a tick consists of 2d + 1 black cells. 



An already painted cell will remain black if painted again. Below you can find an example of the 4 × 9 box, with two ticks of sizes 2 and 3.

<image>

You are given a description of a checkered field of size n × m. Casimir claims that this field came about after he drew some (possibly 0) ticks on it. The ticks could be of different sizes, but the size of each tick is at least k (that is, d ≥ k for all the ticks).

Determine whether this field can indeed be obtained by drawing some (possibly none) ticks of sizes d ≥ k or not.

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number test cases.

The following lines contain the descriptions of the test cases. 

The first line of the test case description contains the integers n, m, and k (1 ≤ k ≤ n ≤ 10; 1 ≤ m ≤ 19) — the field size and the minimum size of the ticks that Casimir drew. The following n lines describe the field: each line consists of m characters either being '.' if the corresponding cell is not yet painted or '*' otherwise.

Output

Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if the given field can be obtained by drawing ticks of at least the given size and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).

Example

Input


8
2 3 1
*.*
...
4 9 2
*.*.*...*
.*.*...*.
..*.*.*..
.....*...
4 4 1
*.*.
****
.**.
....
5 5 1
.....
*...*
.*.*.
..*.*
...*.
5 5 2
.....
*...*
.*.*.
..*.*
...*.
4 7 1
*.....*
.....*.
..*.*..
...*...
3 3 1
***
***
***
3 5 1
*...*
.***.
.**..


Output


NO
YES
YES
YES
NO
NO
NO
NO

Note

The first sample test case consists of two asterisks neither of which can be independent ticks since ticks of size 0 don't exist.

The second sample test case is already described in the statement (check the picture in the statement). This field can be obtained by drawing ticks of sizes 2 and 3, as shown in the figure.

The field in the third sample test case corresponds to three ticks of size 1. Their center cells are marked with \color{blue}{blue}, \color{red}{red} and \color{green}{green} colors: *.*.  
---  
*\color{blue}{*}**  
.\color{green}{*}\color{red}{*}.  
....  
  
The field in the fourth sample test case could have been obtained by drawing two ticks of sizes 1 and 2. Their vertices are marked below with \color{blue}{blue} and \color{red}{red} colors respectively: .....  
---  
*...*  
.*.*.  
..\color{red}{*}.*  
...\color{blue}{*}.  
  
The field in the fifth sample test case can not be obtained because k = 2, and the last asterisk in the fourth row from the top with coordinates (4, 5) can only be a part of a tick of size 1.

The field in the sixth sample test case can not be obtained because the top left asterisk (1, 1) can't be an independent tick, since the sizes of the ticks must be positive, and cannot be part of a tick with the center cell in the last row, since it is separated from it by a gap (a point, '.') in (2, 2).

In the seventh sample test case, similarly, the field can not be obtained by the described process because the asterisks with coordinates (1, 2) (second cell in the first row), (3, 1) and (3, 3) (leftmost and rightmost cells in the bottom) can not be parts of any ticks.
import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main{

    static int mod = (int) (Math.pow(10, 9)+7);
	static final int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
	static final int[] dx8 = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
	static final int[] dx9 = { -1, -1, -1, 0, 0, 0, 1, 1, 1 }, dy9 = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
	static final int inf = Integer.MAX_VALUE / 2;
	static final long infL = Long.MAX_VALUE / 3;
	static final double infD = Double.MAX_VALUE / 3;
	static final double eps = 1e-10;
	static final double pi = Math.PI;
    static List<Integer> primeNumbers = new ArrayList<>();

    public static void solve(int lx, int ly, int rx, int ry, char[][] inp, boolean[][] t){

        //now i have to see the path
        int count = 0;
        while(ly != ry){
            //we will perfrom some operations
            lx++;
            rx++;
            ly++;
            ry--;

            if(ry < ly) return;

            if(lx >= inp.length) return;
            if(inp[lx][ly] != '*' || inp[rx][ry] != '*') return;

            //don't even budge forward
            count++;
        }

        //otherwise we would have reached the desired position we would want for sure
        //let's think now 
        //i really don't like this fujntion for some reasons
        while(count-- > -1){
            t[lx][ly] = true;
            t[rx][ry] = true;

            lx--;
            rx--;
            ly--;
            ry++;
        }

    }
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        int test = sc.nextInt();
        while(test --> 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int kk = sc.nextInt();

            char[][] inp = new char[n][m];
            boolean[][] t = new boolean[n][m];

            for(int i= 0; i < n; i++){
                inp[i] = sc.nextLine().toCharArray();
            }

            //now i have the input ready for sure, let's move forward for sure
            for(int i= 0; i < n; i++){
                for(int j = 0; j < m; j++){

                    //we are at one single star
                    if(inp[i][j] != '*') continue;

                    for(int k = j + (2*kk-1); k < m; k++){
                        if(inp[i][k] == '*'){
                            solve(i, j, i, k, inp, t);
                        }
                    }

                }
            }
    
            // for(int i = 0; i < t.length; i++){
            //     for(int j = 0; j < m; j++){
            //         out.print(t[i][j] ? 1 : 0);
            //         out.print(" ");
            //     }
            //     out.println();
            // }
            
            boolean flag = true;
            for(int i= 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(inp[i][j] == '*' && t[i][j] == false){
                        flag = false;
                        break;
                    }
                }
                if(!flag) break;
            }

            out.println(flag ? "YES" : "NO");

        }
    
        out.close();
    }

    //-------------------------------------------------------------------
    //-------------------------------------------------------------------
    //-------------------------------------------------------------------
    //-------------------------------------------------------------------
    //-------------------------------------------------------------------

    //fast java implementation for sure
    public static class Graph{
        public int V;
        public ArrayList<ArrayList<Integer>> edges;

        Graph(int V){
            this.V  = V;
            edges = new ArrayList<>(V+1);
            for(int i= 0; i <= V; i++){
                edges.add(new ArrayList<>());
            }
        }

        ///single sided this for sure
        public void addEdge(int from , int to){
            edges.get(from).add(to);
        }
    }

    public static class DisjointUnionSets {
        int[] rank, parent;
        int n;
      
        // Constructor
        public DisjointUnionSets(int n)
        {
            rank = new int[n];
            parent = new int[n];
            this.n = n;
            makeSet();
        }
      
        // Creates n sets with single item in each
        void makeSet()
        {
            for (int i = 0; i < n; i++) {
                // Initially, all elements are in
                // their own set.
                parent[i] = i;
            }
        }
      
        // Returns representative of x's set
        int find(int x)
        {
            // Finds the representative of the set
            // that x is an element of
            if (parent[x] != x) {
                // if x is not the parent of itself
                // Then x is not the representative of
                // his set,
                parent[x] = find(parent[x]);
      
                // so we recursively call Find on its parent
                // and move i's node directly under the
                // representative of this set
            }
      
            return parent[x];
        }
      
        // Unites the set that includes x and the set
        // that includes x
        void union(int x, int y)
        {
            // Find representatives of two sets
            int xRoot = find(x), yRoot = find(y);
      
            // Elements are in the same set, no need
            // to unite anything.
            if (xRoot == yRoot)
                return;
      
            // If x's rank is less than y's rank
            if (rank[xRoot] < rank[yRoot])
      
                // Then move x under y  so that depth
                // of tree remains less
                parent[xRoot] = yRoot;
      
            // Else if y's rank is less than x's rank
            else if (rank[yRoot] < rank[xRoot])
      
                // Then move y under x so that depth of
                // tree remains less
                parent[yRoot] = xRoot;
      
            else // if ranks are the same
            {
                // Then move y under x (doesn't matter
                // which one goes where)
                parent[yRoot] = xRoot;
      
                // And increment the result tree's
                // rank by 1
                rank[xRoot] = rank[xRoot] + 1;
            }
        }
    }

    //with mod
    public static long power(long x, long y)
    {
        long res = 1L;     // Initialize result
        while (y > 0)
        {
            // If y is odd, multiply x with result
            if ((y & 1) != 0){
                x %= mod;
                res %= mod;
                res = (res * x)%mod;
            }
            // y must be even now
            y = y >> 1; // y = y/2
            x%= mod;
            x = (x * x)%mod;  // Change x to x^2
        }
        // 550193677
        return res%mod;
    }

    //without mod
    public static long power2(long x, long y)
    {
        long res = 1L;     // Initialize result
        while (y > 0)
        {
            // If y is odd, multiply x with result
            if ((y & 1) != 0){
                res = (res * x);
            }
            // y must be even now
            y = y >> 1; // y = y/
            x = (x * x);
        }
        // 550193677
        return res;
    }

    public static class segmentTree{

        public long[] arr;
        public long[] tree;
        public long[] lazy;

        segmentTree(long[] array){
            int n = array.length;
            arr = new long[n];
            for(int i= 0; i < n; i++) arr[i] = array[i];
            tree = new long[4*n + 1];
            lazy = new long[4*n + 1];
        }

        public  void build(int[]arr, int s, int e, int[] tree, int index){

            if(s == e){
                tree[index] = arr[s];
                return;
            }
    
            //otherwise divide in two parts and fill both sides simply
            int mid = (s+e)/2;
            build(arr, s, mid, tree, 2*index);
            build(arr, mid+1, e, tree, 2*index+1);
    
            //who will build the current position dude
            tree[index] = Math.min(tree[2*index], tree[2*index+1]);
        }
    
        public  int query(int sr, int er, int sc, int ec, int index, int[] tree){
            
            if(lazy[index] != 0){
                tree[index] += lazy[index];
    
                if(sc != ec){
                    lazy[2*index+1] += lazy[index];
                    lazy[2*index] += lazy[index];
                }
    
                lazy[index] = 0;
            }
            
            //no overlap
            if(sr > ec || sc > er) return Integer.MAX_VALUE;
    
            //found the index baby
            if(sr <= sc && ec <= er) return tree[index];
    
            //finding the index on both sides hehehehhe
            int mid = (sc + ec)/2;
            int left = query(sr, er, sc, mid, 2*index, tree);
            int right = query(sr, er, mid+1, ec, 2*index + 1, tree);
    
            return Integer.min(left, right);
        }
    
        //now we will do point update implementation
        //it should be simple then we expected for sure
        public  void update(int index, int indexr, int increment, int[] tree, int s, int e){
    
            if(lazy[index] != 0){
                tree[index] += lazy[index];
    
                if(s != e){
                    lazy[2*index+1] = lazy[index];
                    lazy[2*index] = lazy[index];
                }
                
                lazy[index] = 0;
            }
    
            //no overlap
            if(indexr < s || indexr > e) return;
    
            //found the required index
            if(s == e){
                tree[index] += increment;
                return;
            } 
    
            //search for the index on both sides
            int mid = (s+e)/2;
            update(2*index, indexr, increment, tree, s, mid);
            update(2*index+1, indexr, increment, tree, mid+1, e);
    
            //now update the current range simply
            tree[index] = Math.min(tree[2*index+1], tree[2*index]);
        }
    
        public  void rangeUpdate(int[] tree , int index, int s, int e, int sr, int er, int increment){
    
            //if not at all in the same range
            if(e < sr || er < s) return;
    
            //complete then also move forward
            if(s == e){
                tree[index] += increment;
                return;
            }
    
            //otherwise move in both subparts
            int mid = (s+e)/2;
            rangeUpdate(tree, 2*index, s, mid, sr, er, increment);
            rangeUpdate(tree, 2*index + 1, mid+1, e, sr, er, increment);
    
            //update current range too na
            //i always forget this step for some reasons hehehe, idiot
            tree[index] = Math.min(tree[2*index], tree[2*index + 1]);
        }
        
        public  void rangeUpdateLazy(int[] tree, int index, int s, int e, int sr, int er, int increment){
            
            //update lazy values
            //resolve lazy value before going down
            if(lazy[index] != 0){
                tree[index] += lazy[index];
    
                if(s != e){
                    lazy[2*index+1] += lazy[index];
                    lazy[2*index] += lazy[index];
                }
    
                lazy[index] = 0;
            }
    
            //no overlap case
            if(sr > e || s > er) return;
    
            //complete overlap
            if(sr <= s && er >= e){
                tree[index] += increment;
    
                if(s != e){
                    lazy[2*index+1] += increment;
                    lazy[2*index] += increment;
                }
                return;
            }
    
            //otherwise go on both left and right side and do your shit
            int mid = (s + e)/2;
            rangeUpdateLazy(tree, 2*index, s, mid, sr, er, increment);
            rangeUpdateLazy(tree, 2*index + 1, mid+1, e, sr, er, increment);
    
            tree[index] = Math.min(tree[2*index+1], tree[2*index]);
            return;
    
        }
    
    }

    //prime sieve
    public static void primeSieve(int n){
        BitSet bitset = new BitSet(n+1);
        for(long i = 0; i < n ; i++){
            if (i == 0 || i == 1) {
                bitset.set((int) i);
                continue;
            }
            if(bitset.get((int) i)) continue;
            primeNumbers.add((int)i);
            for(long j = i; j <= n ; j+= i)
                bitset.set((int)j);
        }
    }

    //number of divisors
    public static int countDivisors(long number){
        if(number == 1) return 1;
        List<Integer> primeFactors = new ArrayList<>();
        int index = 0;
        long curr = primeNumbers.get(index);
        while(curr * curr <= number){
            while(number % curr == 0){
                number = number/curr;
                primeFactors.add((int) curr);
            }    
            index++;
            curr = primeNumbers.get(index);
        }

        if(number != 1) primeFactors.add((int) number);
        int current = primeFactors.get(0);
        int totalDivisors = 1;
        int currentCount = 2;
        for (int i = 1; i < primeFactors.size(); i++) {
            if (primeFactors.get(i) == current) {
                currentCount++;
            } else {
                totalDivisors *= currentCount;
                currentCount = 2;
                current = primeFactors.get(i);
            }
        }
        totalDivisors *= currentCount;
        return totalDivisors;
    }

    //now adding next permutation function to java hehe
    public static boolean next_permutation(int[] p) {
        for (int a = p.length - 2; a >= 0; --a)
          if (p[a] < p[a + 1])
            for (int b = p.length - 1;; --b)
              if (p[b] > p[a]) {
                int t = p[a];
                p[a] = p[b];
                p[b] = t;
                for (++a, b = p.length - 1; a < b; ++a, --b) {
                  t = p[a];
                  p[a] = p[b];
                  p[b] = t;
                }
                return true;
              }
        return false;
    }

    //finding the value of NCR in O(RlogN) time and O(1) space
    public static long getNcR(int n, int r)
    {
        long p = 1, k = 1;
        if (n - r < r) r = n - r;

        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
                long m = __gcd(p, k);
                p /= m;
                k /= m;
                n--;
                r--;
            }
        }
        else {
            p = 1;
        }
        return p;
    }

    public static void sort(long[] a) {
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
 
    //for ncr calculator
    public static long __gcd(long n1, long n2)
    {
        long gcd = 1;
        for (int i = 1; i <= n1 && i <= n2; ++i) {
            // Checks if i is factor of both integers
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }



    //is vowel function 
    public static boolean isVowel(char c)
    {
        return (c=='a' || c=='A' || c=='e' || c=='E' || c=='i' || c=='I' || c=='o' || c=='O' ||     c=='u' || c=='U');
    }   

    //two add two big numbers with some mod 
    public static int add(int a, int b) {
		a+=b;
		if (a>=mod) return a-mod;
		return a;
	}
	
    //two sub two numbers
	public static int sub(int a, int b) {
		a-=b;
		if (a<0) a+=mod;
		else if (a>=mod) a-=mod;
		return a;
	}
 
    //to sort the array with better method
	public static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
    //for calculating binomialCoeff
    public static int binomialCoeff(int n, int k)
    {
        int C[] = new int[k + 1];
        // nC0 is 1
        C[0] = 1;
        for (int i = 1; i <= n; i++) {
            // Compute next row of pascal
            // triangle using the previous row
            for (int j = Math.min(i, k); j > 0; j--)
                C[j] = C[j] + C[j - 1];
        }
        return C[k];
    }

    //Pair with int int 
    public static class Pair{

        public int a;
        public int b;

        Pair(int a , int b){
            this.a = a;
            this.b = b;
        }

        @Override
        public String toString(){
            return a + " -> " + b; 
        }
    }

    //Triplet with int int int
    public static class Triplet{

        public int a;
        public int b;
        public int c;

        Triplet(int a , int b, int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }

        @Override
        public String toString(){
            return a + " -> " + b; 
        }
    }

    //Shortcut function
    public static long lcm(long a , long b){
        return a * (b/gcd(a,b));
    }

    //let's make one for calculating lcm basically
    public static int lcm(int a , int b){
        return (a * b)/gcd(a,b);
    }

    //int version for gcd
    public static int gcd(int a, int b){
        if(b == 0)
            return a;
            
        return gcd(b , a%b);
    }

    //long version for gcd
    public static long gcd(long a, long b){
        if(b == 0)
            return a;

        return gcd(b , a%b);
    }

    //swapping two elements in an array
    public static void swap(int[] arr, int left , int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    //
     //for char array
     public static void swap(char[] arr, int left , int right){
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    //reversing an array
    public static void reverse(int[] arr){
        int left = 0;
        int right = arr.length-1;

        while(left <= right){
            swap(arr, left,right);
            left++;
            right--;
        }
    }

     
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
      
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
    
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
    
        int nextInt() {
            return Integer.parseInt(next());
        }
    
        long nextLong() {
            return Long.parseLong(next());
        }
    
        double nextDouble() {
            return Double.parseDouble(next());
        }
    
        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
   //--------------------------------------------------------
}