use std::fmt;
use std::io::stdin;
use std::io::BufRead;
use std::str;
use std::str::FromStr;
use std::vec::Vec;
use std::slice::IterMut;
use std::ops::{Index,IndexMut};

#[derive(Clone)]
pub struct UncheckedVec<T> where T: Clone {
    inner:Vec<T>
}
impl<T> UncheckedVec<T> where T: Clone {
    pub fn new() -> UncheckedVec<T> {
        UncheckedVec {
            inner:Vec::new()
        }
    }

    pub fn with_capacity(size:usize) -> UncheckedVec<T> {
        UncheckedVec {
            inner:Vec::with_capacity(size)
        }
    }

    pub fn resize(&mut self,size:usize,v:T) {
        self.inner.resize(size,v);
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        self.inner.iter_mut()
    }

    pub unsafe fn get_unchecked_mut(&mut self,index:usize) -> &mut T {
        self.inner.get_unchecked_mut(index)
    }
}
impl<T> Index<usize> for UncheckedVec<T> where T: Clone {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        unsafe { self.inner.get_unchecked(index) }
    }
}
impl<T> IndexMut<usize> for UncheckedVec<T> where T: Clone {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        unsafe { self.inner.get_unchecked_mut(index) }
    }
}
fn main() {
    const MAX_V:usize = 186;
    const K:usize = 16;

    let stdin = stdin();
    let mut scan = InputScanner::new(stdin.lock(), 256);

    let h:usize = scan.next();
    let w:usize = scan.next();

    let a:Vec<Vec<char>> = (0..h).map(|_| scan.next::<String>().chars().collect()).collect();

    let mut sum:Vec<Vec<i64>> = (0..(h+1)).map(|_| (0..(w+1)).map(|_| 0).collect::<Vec<i64>>()).collect();

    for y in 0..h {
        for x in 0..w {
            sum[y+1][x+1] = sum[y][x+1] + sum[y+1][x] - sum[y][x] + if a[y][x] == '#' {
                1
            } else {
                0
            };
        }
    }

    let mut dp1:UncheckedVec<UncheckedVec<UncheckedVec<UncheckedVec<u16>>>> = UncheckedVec::with_capacity(MAX_V);
    {
        let mut k = UncheckedVec::new();
        k.resize(2,0);

        let mut h1 = UncheckedVec::with_capacity(MAX_V);
        h1.resize(MAX_V,k);

        let mut w2 = UncheckedVec::with_capacity(MAX_V);

        w2.resize(MAX_V,h1);

        dp1.resize(MAX_V,w2);
    }

    let mut dp2:UncheckedVec<UncheckedVec<UncheckedVec<UncheckedVec<u16>>>> = UncheckedVec::with_capacity(MAX_V);
    {
        let mut k = UncheckedVec::new();
        k.resize(2,0);

        let mut w1 = UncheckedVec::with_capacity(MAX_V);
        w1.resize(MAX_V,k);

        let mut h2 = UncheckedVec::with_capacity(MAX_V);

        h2.resize(MAX_V,w1);

        dp2.resize(MAX_V,h2);
    }

    for w1 in 0..(w+1) {
        for w2 in w1..(w+1) {
            let mut h2 = 0;

            for h1 in 0..(h+1) {
                if h2 < h1 {
                    h2 = h1;
                }

                while h2 < h {
                    let c = sum[h1][w1] + sum[h2+1][w2] - sum[h1][w2] - sum[h2+1][w1];

                    if c == 0 || c == (h2+1 - h1) as i64 * (w2 - w1) as i64 {
                        h2 += 1;
                    } else {
                        break;
                    }
                }

                dp1[w1][w2][h1][0] = h2 as u16;
            }
        }
    }

    for h1 in 0..(h+1) {
        for h2 in h1..(h+1) {
            let mut w2 = 0;

            for w1 in 0..(w+1) {
                if w2 < w1 {
                    w2 = w1;
                }

                while w2 < w {
                    let c = sum[h1][w1] + sum[h2][w2+1] - sum[h1][w2+1] - sum[h2][w1];

                    if c == 0 || c == (h2 - h1) as i64 * (w2+1 - w1) as i64 {
                        w2 += 1;
                    } else {
                        break;
                    }
                }

                dp2[h1][h2][w1][0] = w2 as u16;
            }
        }
    }

    let mut answer = K;

    for k in 0..K {
        for w1 in 0..(w+1) {
            for w2 in w1..(w+1) {
                for h1 in 0..(h+1) {
                    let h = dp1[w1][w2][h1][k % 2];

                    if dp1[w1][w2][h1][(k + 1) % 2] < dp1[w1][w2][h as usize][k % 2] {
                        dp1[w1][w2][h1][(k + 1) % 2] = dp1[w1][w2][h as usize][k % 2];
                    }
                }

                let mut h2 = 0;

                for h1 in 0..(h+1) {
                    if h2 < h1 {
                        h2 = h1;
                    }

                    while h2 < h {
                        if dp2[h1][h2+1][dp2[h1][h2+1][w1][k%2] as usize][k%2] >= w2 as u16 {
                            h2 += 1;
                        } else {
                            break;
                        }
                    }

                    if dp1[w1][w2][h1][(k+1)%2] < h2 as u16 {
                        dp1[w1][w2][h1][(k + 1) % 2] = h2 as u16;
                    }
                }
            }
        }

        for h1 in 0..(h+1) {
            for h2 in h1..(h+1) {
                for w1 in 0..(w+1) {
                    let w = dp2[h1][h2][w1][k % 2];

                    if dp2[h1][h2][w1][(k + 1) % 2] < dp2[h1][h2][w as usize][k % 2] {
                        dp2[h1][h2][w1][(k + 1) % 2] = dp2[h1][h2][w as usize][k % 2];
                    }
                }

                let mut w2 = 0;

                for w1 in 0..(w+1) {
                    if w2 < w1 {
                        w2 = w1;
                    }

                    while w2 < w {
                        if dp1[w1][w2+1][dp1[w1][w2+1][h1][k%2] as usize][k%2] >= h2 as u16 {
                            w2 += 1;
                        } else {
                            break;
                        }
                    }

                    if dp2[h1][h2][w1][(k+1)%2] < w2 as u16 {
                        dp2[h1][h2][w1][(k + 1) % 2] = w2 as u16;
                    }
                }
            }
        }

        if dp1[0][w][0][k%2] == h as u16 || dp2[0][h][0][k%2] == w as u16 {
            answer = k;
            break;
        }

        for (it1,it2) in dp1.iter_mut().zip(dp2.iter_mut()) {
            for (it1,it2) in it1.iter_mut().zip(it2.iter_mut()) {
                for (it1,it2) in it1.iter_mut().zip(it2.iter_mut()) {
                    unsafe {
                        *it1.get_unchecked_mut(k % 2) = 0;
                        *it2.get_unchecked_mut(k % 2) = 0;
                    }
                }
            }
        }
    }

    println!("{}",answer);
}
struct InputScanner<R: BufRead> {
    reader: R,
    buf: Vec<u8>, // Should never be empty
    pos: usize,   // Should never be out of bounds as long as the input ends with '\n'
}
impl<R: BufRead> InputScanner<R> {
    fn new(reader: R, capacity: usize) -> Self {
        InputScanner {
            reader: reader,
            buf: Vec::with_capacity(capacity),
            pos: 0,
        }
    }

    #[inline]
    fn next<T: FromStr>(&mut self) -> T
        where
            T::Err: fmt::Debug,
    {
        if self.buf.is_empty() {
            self._read_next_line();
        }
        let mut start = None;
        loop {
            match (self.buf[self.pos], start.is_some()) {
                (b' ', true) | (b'\n', true) | (b'\r', true) => break,
                (_, true) | (b' ', false) => self.pos += 1,
                (b'\n', false) | (b'\r', false) => self._read_next_line(),
                (_, false) => start = Some(self.pos),
            }
        }
        let target = &self.buf[start.unwrap()..self.pos];
        unsafe { str::from_utf8_unchecked(target) }.parse().unwrap()
    }

    #[inline]
    fn _read_next_line(&mut self) {
        self.pos = 0;
        self.buf.clear();
        if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {
            panic!("Reached EOF");
        }
    }
}

Measured memory_bytes: 463228