marais

Vous êtes l'agent James Tomb et Sa Majesté vous a demandé de capturer le terrible Goldsinger qui se cache au milieu d'un marais. Très attaché à votre prestance en toute condition, vous souhaitez procéder à l'arrestation en évitant de trop salir votre smoking. Dans ce marais rectangulaire composé de cases vides ou marécageuses, vous devez trouver un chemin qui mène à Goldsinger en empruntant le minimum de cases marécageuses. Vous ne pouvez vous déplacer que verticalement ou horizontalement. Goldsinger et vous même êtes initialement sur des cases vides.

Entrée: On vous donne une série d'instances. Pour chaque instance, sur la première ligne, un entier H (entre 1 et 100 inclus) donne le nombre de lignes du marais. Sur la deuxième ligne, un entier L (entre 1 et 100 inclus) donne le nombre de colonnes du marais. Sur les H lignes suivantes, il y a L caractères: 'X' représente une case marécageuse et '.' une case vide. De plus, 'T' représentera votre position initiale et 'G' la position de Goldsinger. Le marais contiendra exactement un caractère 'T' et exactement un caractère 'G'.

Sortie: Pour chaque instance, vous devez afficher sur une ligne le nombre minimum de cases marécageuses à emprunter pour atteindre Goldsinger.

Input

5
5
.T...
.XXX.
.XXX.
.XGX.
.XXX.
10
10
.XX..X....
.XX..X.G..
.XXXXXXXXX
.XXXXXXXXX
.XXXXXXXXX
.XXXXXXXXX
...XT...XX
...X......
...XXXXXX.
..........

Télécharger l'entrée

Output

1
3

Télécharger la sortie