CAO Stage2

All submissions for this problem are available.
Problem Statement
PastIn the year of 2048, the Virtual Reality Massively Multiplayer Online RolePlaying Game (VRMMORPG), Code Art Online (CAO), is released. With the Chef Gear, a virtual reality helmet that stimulates the user's five senses via their brain, players can experience and control their ingame characters with their minds.
On August the 2nd, 2048, all the players log in for the first time, and subsequently discover that they are unable to log out. They are then informed by Code Master, the creator of CAO, that if they wish to be free, they must reach the second stage of the game.
Kirito is a known star player of CAO. You have to help him log out.
PresentStage 2
A map is described by a 2D grid of cells. Each cell is either labelled as a # or a ^. # denotes a wall. A monster exists in a cell if the cell is not a wall and the cell is a centre of PrimeCross (CPC).
 Let L be the number of contiguous ^ to the left of X, in the same row as X.
 R be the number of contiguous ^ to the right of X, in the same row as X.
 T be the number of contiguous ^ above X, in the same column as X.
 B be the number of contiguous ^ below X, in the same column as X.
A cell X is said to be a CPC if there exists a prime number P such that P ≤ minimum of [L, R, T, B].
Note that, there can be many such primes, let N be the number of such primes. That CPC can accommodate N monsters.Note: While computing L, R, T, B for a cell X, you should not count the ^ of the cell X.
Given a map, you have to tell Kirito the number of cells where monsters exist.
FutureHave fun solving other tasks :)
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each case starts with a line containing two space separated integers R, C, denoting the number of rows and columns in the map respectively. The next R lines contain C characters each, describing the map.
Output
For each test case, output a single line containing the number of monsters the map can accommodate.
Constraints
 1 ≤ T ≤ 100
 1 ≤ R ≤ 500
 1 ≤ C ≤ 500
Example
Input: 2 3 10 #^^^^^#^## ^^^^^^^^^^ ^^^^^^^^^# 7 10 ^^^^#^^^^# ^^^^^^^^#^ ^^##^^#^^^ #^^^^^^^#^ ^^#^^^^^^^ ^^^^#^^^^^ ^^^^^^^^^^ Output: 0 3
Author:  kaushik_iska 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CAOS2 
Tags  kaushik_iska, sept13, simple 
Date Added:  16072013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 