Recent compitition (Logicode) CHEF MAKES GOOD PAIRS

Q - there is a N*N square matrix cosisting of three char A,B and C … how many pairs of cells can we select so that if that pair of cells is removed from the sqaure matrix and then it is possible to cover the remaining portion(all remaining cells) of square by 1 X 2 tiles constrain - 1≤N≤1000 problem link.-