Il est statué sans frais, la procédure étant en principe gratuite. Une indemnité de dépens est allouée au recourant qui obtient satisfaction (art.85 al.2 litt.a et f LAVS par renvoi de l'art.69 LAI; 48 al.1
LPJA).
Par ces motifs,
LE TRIBUNAL ADMINISTRATIF
1. Annule la décision entreprise.
2. Renvoie la cause à l'office intimé pour nouvelle décision au sens des
considérants.
3. Alloue au recourant une indemnité de dépens de 400 francs.
4. Statue sans frais.
Neuchâtel, le 10 septembre 1996