King ACE wants to win Lovely kingdom
All submissions for this problem are available.
There is a Kingdom named Lovely and King ACE wants to rule it. Currently, Lovely Kingdom is divided into many states. Each state is governed by the governor of the state. Each state has special force to protect it. King ACE decides to send 1 troop to every state.
Each soldier of special force of each state has special weapon. Each weapon falls into some specific category. This special weapon is recognized by its special ID no. If ID is prime then it falls into category PR, if ID of the weapon is not prime but even no. then it falls into category EV, else it falls into category OD i.e. non-prime odd number. It is given that all the soldiers of one state have weapons of same category.
Now specialty of Lovely kingdom is that no two neighboring states in the kingdom have weapons of same category.
King ACE luckily gets placement of soldiers in the form of square matrix where each cell in the matrix represents ID of particular soldier.
Now king ACE wants you to calculate the minimum number of troops needed to conquer the LOVELY kingdom.
First line contains no. of test cases t. Each of the test-case is as follows.
First line of contains no. of soldiers in Lovely kingdom n.
It is followed by n lines each containing n space separated integers representing the ID of the particular weapon.
For each test case output no of troops needed to conquer Lovely kingdom.
Input: 2 2 12 3 9 6 3 2 4 6 18 3 9 12 17 19 Output: 4 5 Constraints: 1<=t<=10 1<=n<=100 1<=weapon ID<= 10000000
|Time Limit:||5 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.