Adjacent Relative-Prime #s In Grid

[Leroy Quet]

For an n-by-n grid, how many ways are there to place the integers 1
through n^2 in the grid, one integer per grid-square, such that each
integer is relatively prime to the integers adjacent to it
(above/below/right/left)?

( Note: This is not the same as my puzzle I posted yesterday to sci.math 
and rec.puzzles, "GCD=1 Grid-Path Puzzle #1",
since here the integer m doesn't have to be adjacent to the integers
(m +-1).)

An n=5 example:

15  2   5   4   3

22  17  18  19  8

7   6   25  24  11

20  13  12  23  10

21  16  1   14  9 


Thanks,
Leroy Quet