Problem: A mouse encountered a nice big cake and decided to take a walk across it, eating the berries on top of the cake on its way. The cake is rectangular, neatly divided into squares; some of the squares have a berry in them, and some don't.

The mouse is in a bit of a hurry, though, so once she enters the cake from its northwest corner (the top left cell in the input data), she will only go east (right) or south (down), until she reaches the southeast corner (the bottom right cell). She will eat every berry in the squares she passes through, but not in the other squares.

The mouse tries to choose her path so as to maximize the number of berries consumed. However, her haste and hunger might be clouding her judgement, leading her to suboptimal decisions...

Input

The first line of input contains two integers H and W (1 ≤ H, W ≤ 5), separated by a space, — the height and the width of the cake.

The next H lines contain a string of W characters each, representing the squares of the cake in that row: '.' represents an empty square, and '*' represents a square with a berry.

Output

Output the number of berries the mouse will eat following her strategy.

Examples

Input


4 3
*..
.*.
..*
...


Output


3


Input


4 4
.*..
*...
...*
..*.


Output


2


Input


3 4
..**
*...
....


Output


1


Input


5 5
..*..
.....
**...
**...
**...


Output


1

Solution (in JAVA):

Solution:

//package com.live.april_2021.april_fool_day;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class Problem4 {
	String INPUT = "";

	public static void main(String[] args) throws Exception {
		new Problem4().run();
	}

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

		return gcd(b % a, a);
	}

	private void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] split = str.split(" ");
		int rowCount = Integer.parseInt(split[0]);
		int columnCount = Integer.parseInt(split[1]);

		int array[][] = new int[rowCount][columnCount];

		int i = 0;
		for (int k = 0; k < rowCount; k++) {
			str = br.readLine();
			int j = 0;
			for (char ch : str.toCharArray()) {
				if (ch == '*') {
					array[i][j++] = 1;
				} else {
					array[i][j++] = 0;
				}
			}
			i++;
		}

		int a = 0;
		int b = 0;

		int answer = 0;
		if (array[0][0] == 1) {
			answer++;
		}
		while (a != rowCount && b != columnCount) {
			if (a == rowCount - 1) {
				b++;
			} else if (b == columnCount - 1) {
				a++;
			} else if (array[a][b + 1] == 1) {
				b++;
			} else if (array[a + 1][b] == 1) {
				a++;
			} else {
				b++;
			}
			if (a != rowCount && b != columnCount) {
				if (array[a][b] == 1) {
					answer++;
				}
			}

		}
		System.out.println(answer);

	}

	InputStream is;
	PrintWriter out;

	void run() throws Exception {
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nextDouble() {
		return Double.parseDouble(nextString());
	}

	private char nextCharactor() {
		return (char) skip();
	}

	private String nextString() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b !=
									// ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] nextString(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nextMap(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = nextString(m);
		return map;
	}

	private int[] nextIntArr(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	private int nextInt() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nextLong() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = true;// System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}