Le Quang Duy

  C2. Errich-Tac-Toe (Hard Version) time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output The only difference between the easy and hard versions is that tokens of type   O   do not appear in the input of the easy version. Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces. In a Tic-Tac-Toe grid, there are   n n   rows and   n n   columns. Each cell of the grid is either empty or contains a token. There are two types of tokens:   X   and   O . If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration. The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. In an operation, you can change an   X   to an   O , or an   O   to an   X . Let   k k   denote the total number of tokens in the grid. Your task is to make the gri

  Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces. In a Tic-Tac-Toe grid, there are  n n  rows and  n n  columns. Each cell of the grid is either empty or contains a token. There are two types of tokens:  X  and  O . If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration. The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. In an operation, you can change an  X  to an  O , or an  O  to an  X . Let  k k  denote the total number of tokens in the grid. Your task is to make the grid a  draw  in at most  ⌊ k 3 ⌋ ⌊ k 3 ⌋  (rounding down) operations. You are  not required  to minimize the number of operations. Input The first line contains a single integer  t t  ( 1 ≤ t ≤ 100 1 ≤ t ≤ 100 ) — the number of test cases. The first line of each test case contains a single i