Faits: Faits: A. A._, né le 30 janvier 1967, est double-national suisse et français. Il a déposé ses papiers de légitimation à La Chaux-de-Fonds le 15 mars 1998. Un livret de service a été établi à son nom et il a été informé qu'il était astreint au paiement de la taxe d'exemption de l'obligation de servir (ci-après: la taxe d'exemption). Le 20 février 2003, le Service de la sécurité civile et militaire du canton de Neuchâtel (ci-après: le Service cantonal) lui a notifié les taxes d'exemption pour les années 1998 à 2001. Le 30 juillet 2003 puis le 16 juin 2004, les taxes d'exemption pour les années 2002 et 2003 lui ont été notifiées. Le 11 mai 2004, le Service cantonal a rappelé à l'intéressé que le chef de la Section militaire de La Chaux-de-Fonds avait tenté sans succès d'obtenir les documents français nécessaires à son exonération de la taxe d'exemption. Il l'a également rendu attentif au fait que la réclamation verbale qu'il avait soulevée n'était pas valable. Par courrier du 24 juin 2005 au Service cantonal, A._ a indiqué qu'il avait accompli son service militaire en France et qu'il n'était pas soumis à la taxe d'exemption. Le 25 août 2005, le Service cantonal a rejeté la réclamation de A._ contre la fixation des taxes des années d'assujettissement 1998 à 2003. Il a relevé que, pour être exonéré de la taxe d'exemption, l'intéressé devait être au bénéfice de la Convention conclue le 16 novembre 1995 entre le Conseil fédéral suisse et le Gouvernement de la République française relative au service militaire des double-nationaux (ci-après: la Convention; RS 0.141.134.92) et être "affecté aux double-nationaux non incorporés". Or celui-ci n'avait pas produit de décision de l'Etat major de conduite de l'armée en ce sens. Le 25 août 2005, le Service cantonal a rejeté la réclamation de A._ contre la fixation des taxes des années d'assujettissement 1998 à 2003. Il a relevé que, pour être exonéré de la taxe d'exemption, l'intéressé devait être au bénéfice de la Convention conclue le 16 novembre 1995 entre le Conseil fédéral suisse et le Gouvernement de la République française relative au service militaire des double-nationaux (ci-après: la Convention; RS 0.141.134.92) et être "affecté aux double-nationaux non incorporés". Or celui-ci n'avait pas produit de décision de l'Etat major de conduite de l'armée en ce sens. B. Le 20 décembre 2005, sur recours de l'intéressé, le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a annulé la décision sur réclamation du Service cantonal du 25 août 2005. Il a considéré que, faute de réclamation écrite présentée par l'intéressé dans le délai légal de trente jours suivant leur notification, les décisions de taxation litigieuses étaient entrées en force et que c'était donc à tort que le Service cantonal était entré en matière sur la réclamation du 24 juin 2005. Le 20 janvier 2006, le Service cantonal a notifié une nouvelle décision à A._, déclarant sa réclamation du 24 juin 2005 irrecevable. Le 7 mars 2006, le Tribunal administratif a rejeté le recours de l'intéressé contre la décision précitée. Il a rappelé qu'il s'était déjà prononcé sur la recevabilité de la réclamation de l'intéressé dans sa décision du 20 décembre 2005, dont il a confirmé les considérants. Le 7 mars 2006, le Tribunal administratif a rejeté le recours de l'intéressé contre la décision précitée. Il a rappelé qu'il s'était déjà prononcé sur la recevabilité de la réclamation de l'intéressé dans sa décision du 20 décembre 2005, dont il a confirmé les considérants. C. A._ a porté sa cause devant le Tribunal fédéral. Il conclut implicitement à l'annulation de la décision du Tribunal administratif du 7 mars 2006. Il allègue qu'il a pris contact avec le chef de la Section militaire de La Chaux-de-Fonds au moment du dépôt de ses papiers en Suisse pour être exonéré de la taxe d'exemption et lui a fait parvenir tous les documents nécessaires. Le Tribunal administratif n'a pas formulé d'observations sur le recours. Le Service cantonal a déclaré maintenir sa prise de position relative à sa décision sur réclamation du 20 janvier 2006. L'Administration fédérale des contributions, Section taxe d'exemption de l'obligation de servir, a proposé le rejet du recours. 