Vanishing Squares

Consider a square grid made of matchsticks. Four matches are needed to make a single square. To break the square, you can remove any single match. Twelve matches are needed to make a 2x2 grid of squares (6 horizontal and 6 vertical.) There are 5 squares in such a grid, four 1x1 and one 2x2. To eliminate all squares, three matches must be removed (an external match must be removed to break the 2x2 square, but this leaves three 1x1 squares, and at least two more matches must be removed to leave no full squares.) 
 __ __ __
|__|__|__|
|__|__|__|
|__|__|__|
 What is the fewest number of matches which must be removed to break all squares - of any size - in:
  1. a 3x3 grid (originally 24 matches, as shown)?
  2. a 4x4 grid (originally 40 matches)?
  3. a 5x5 grid (originally 60 matches)?

Source: Based on "Vanishing Trick" in Michael Holt's Math Puzzles & Games, Volume 2, Page 44.

Solutions were received from many people. For the three puzzles above, the answers are 6, 9 and 14 sticks respectively. Al Zimmermann wrote a program which showed the first two are minimums. Denis Borris showed a nice way to solve successive squares: 
+---+
|   |
+ 1 +
match 1 removed

+---+ 2 +
|   |   |
+ 1 +---+
|   |   |
+---+ 3 +
match 2 and 3 removed

+---+ 2 +---+
|   |   |   |
+ 1 +---+ 4 +
|   |   |   |
+---+ 3 + 5 +
|   |   |   |
+ 6 +---+---+
match 4 5 and 6 removed

+---+ 2 +---+---+
|   |   |   |   |
+ 1 +---+ 4 + 7 +
|   |   |   |   |
+---+ 3 + 5 +---+
|   |   |   |   |
+ 6 +---+---+ 8 +
|   |   9   |   |
+---+---+---+---+
match 7 8 and 9 removed


 +---+ 2 +---+---+-10+
 |   |   |   |   |   |
 + 1 +---+ 4 + 7 +---+
 |   |   |   |   |   |
 +---+ 3 + 5 +---+-11+
 |   |   |   |   |   |
 + 6 +---+---+ 8 +---+
 |   |   9   |   |   |
 +---+---+---+---+-12+
 |   14  |   13  |   |
 =---+---+---+---+---+
match 10-14 removed

I'll leave my contribution at showing how easy it is to get to a
solution for an 8by8, using copies of the 4by4 layout after the
initial removal of the minimum of 9 matches.

Explanations: 
1- I used stars to make it easier to "see" the four 4by4's
2- the digits in the diagram represent removed matches

Notice that all that needs to be done is (going clockwise)
placing the 3 additional layouts after a quarter turn:

  ***** 2 *************************
  *   |   |   4   *   |   |   1   *
  * 1 +---+---+---* 9 + 6 +---+---*
  *   |   3   |   *   |   |   |   2
  *---+---+---+ 7 *---+ 5 + 3 +---*
  *   6   5   |   *   |   |   |   *
  *---+---+---+---* 8 +---+---+ 4 *
  *   9   |   8   *   |   7   |   *
  *********************************
  *   |   7   |   *   8   |   9   *
  * 4 +---+---+ 8 *---+---+---+---*
  *   |   |   |   *   |   5   6   *
  *---+ 3 + 5 +---* 7 +---+---+---*
  2   |   |   |   *   |   3   |   *
  *---+---+ 6 + 9 *---+---+---+ 1 *
  *   1   |   |   *   4   |   |   *
  ************************* 2 *****
[KD: Denis wanted me to point out that this 8x8 may not necessarily be a minimal solution with 36 matches removed, but for now it's the best I have.]
Mail to Ken