Given a grid of size 3 x n (n <= 10^5), consists of empty cells (marked with dot '.'), occupied cells (marked with sharp '#'), asterisks (marked with '"'), and many character 'S' and 'T'. A path connecting S and T is good if the following conditions hold: - It doesn't pass through any other S and T. - It doesn't pass through occupied cell ('#') - It passes through at most 1 asterisk. Moreover, paths are not allowed to intersect each other. Calculate the maximum number of path in the grid.

I haven't got any idea for this problem. Thank you and appreciate for any help.