Faits:
Faits:
A. A.a D._, né en 1962, est en Suisse depuis 1989 sans titre de séjour. Le 23 février 1998, il a déposé une demande de prestations auprès de l'Office cantonal genevois de l'assurance-invalidité (OCAI).
Par prononcé du 5 novembre 2002, l'OCAI a avisé la caisse cantonale genevoise de compensation qu'elle avait constaté chez l'assuré une invalidité de 70 % depuis le 1er novembre 1997 et l'a invitée à exécuter les tâches fixées par la circulaire de l'Office fédérale des assurances sociales sur la procédure dans l'assurance-invalidité; au prononcé était jointes une motivation de décision et une indication des voies de droit. Copies de ce courrier et de ses annexes ont été adressées à l'assuré.
A.b Par décision du 14 avril 2003, l'OCAI a rejeté la demande au motif que l'assuré ne remplissait pas les conditions d'assurance, après que la caisse de compensation lui eut signifié que l'assuré ne comptait aucune année de cotisations.
Par décision du 30 octobre 2003, l'OCAI a rejeté l'opposition formée par l'assuré contre sa décision. En bref, il a considéré que l'opposant ne pouvait se prévaloir d'une décision entrée en force de chose décidée au titre du prononcé du 5 novembre 2002 et qu'il n'était pas à même de rapporter la preuve qu'il satisfaisait aux conditions générales d'assurance, notamment par la production d'attestations de salaire.
Par décision du 30 octobre 2003, l'OCAI a rejeté l'opposition formée par l'assuré contre sa décision. En bref, il a considéré que l'opposant ne pouvait se prévaloir d'une décision entrée en force de chose décidée au titre du prononcé du 5 novembre 2002 et qu'il n'était pas à même de rapporter la preuve qu'il satisfaisait aux conditions générales d'assurance, notamment par la production d'attestations de salaire.
B. D._ a recouru contre cette décision devant le Tribunal cantonal des assurances sociales du canton de Genève et conclu à l'octroi d'une rente d'invalidité, fondée sur une perte de gain de 70 %, à dater du 1er novembre 1997.
Le 16 mars 2004, la juridiction cantonale a rendu un arrêt "sur partie" dont le dispositif au fond, sous chiffres 2 à 4, a la teneur suivante :
"2. Dit que le prononcé de l'OCAI du 5 novembre 2002 constitue une décision au sens de la loi.
3. Dit que la reconsidération de cet acte est possible, pour autant que les faits allégués par l'OCAI soient établis.
4. Réserve la suite de la procédure."
4. Réserve la suite de la procédure."
C. L'OCAI interjette recours de droit administratif contre ce jugement. Il conclut à son annulation et au renvoi de la cause aux premières juges, et requiert également que soient constatés différents points relatifs à son prononcé, à sa décision sur opposition et à la forme du jugement attaqué.
D._ conclut au rejet du recours et sollicite l'octroi de l'assistance judiciaire, alors que l'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
Considérant en droit:
1. En l'espèce, la nature de la décision attaquée, dont dépend la recevabilité du recours de droit administratif devant le Tribunal fédéral des assurances, pose problème.
1.1 Est finale la décision par laquelle une autorité met fin à la procédure engagée devant elle, qu'il s'agisse d'une décision sur le fond ou d'une décision qui clôt l'action judiciaire en raison d'un motif de procédure. Le jugement partiel proprement dit est celui qui statue sur une partie quantitativement limitée de la prétention litigieuse ou sur l'une des prétentions en cause (en cas de cumul d'actions ou lorsqu'une demande reconventionnelle a été formée en plus de la demande principale). Quant à la décision préjudicielle, elle tranche une question préalable de fond (sur ces notions, cf. <ref-ruling> consid. 1b/cc, 120 Ib 97 consid. 1c, 116 II 82 consid. 2b et les références; Jean-François Poudret, Commentaire de la loi fédérale d'organisation judiciaire, vol. II, n. 1.1.7.1 ad art. 48; Alfred Kölz/Isabelle Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2ème éd., Zurich 1998, ch. 511 et 896). Enfin, la décision incidente se caractérise par le fait qu'elle est prise en cours de procès et qu'elle ne constitue qu'une étape vers la décision finale; elle porte généralement sur une question de procédure; il n'est cependant pas exclu qu'elle tranche un problème de fond (<ref-ruling> consid. 1b; André Grisel, Traité de droit administratif, vol. II, p. 868).
1.2 Dans le cas particulier, la décision attaquée n'est à l'évidence pas un jugement final. Elle n'est pas davantage un jugement partiel sur le fond dès lors qu'elle ne statue pas, même partiellement, sur les droits de l'intimé ou les obligations du recourant. Le dispositif de cette décision qualifie un acte du recourant au plan juridique et rappelle qu'ainsi qualifié, il est susceptible d'être modifié à certaines conditions; il réserve au surplus la suite de la procédure. L'analyse de ce dispositif conduit à admettre que l'on est en présence d'un jugement préjudiciel, dans la mesure où il tranche au fond une question préalable, au demeurant infime, dans le cadre de l'objet litigieux soumis aux premiers juges. Le point de savoir si une telle appréciation juridique, assortie d'un rappel abstrait de droit, est susceptible de donner lieu à un jugement préjudiciel dans le contentieux judiciaire des assurances sociales est pour le moins douteux, au regard des principes de simplicité et de rapidité que doit revêtir la procédure dans ce domaine (art. 61 lit. a LPGA; Ueli Kieser, ATSG-Kommentar, Zurich 2003, ch. 21 ss ad art. 61; pour l'ancien droit <ref-ruling>). Il peut néanmoins rester indécis pour les raisons qui suivent.
1.2 Dans le cas particulier, la décision attaquée n'est à l'évidence pas un jugement final. Elle n'est pas davantage un jugement partiel sur le fond dès lors qu'elle ne statue pas, même partiellement, sur les droits de l'intimé ou les obligations du recourant. Le dispositif de cette décision qualifie un acte du recourant au plan juridique et rappelle qu'ainsi qualifié, il est susceptible d'être modifié à certaines conditions; il réserve au surplus la suite de la procédure. L'analyse de ce dispositif conduit à admettre que l'on est en présence d'un jugement préjudiciel, dans la mesure où il tranche au fond une question préalable, au demeurant infime, dans le cadre de l'objet litigieux soumis aux premiers juges. Le point de savoir si une telle appréciation juridique, assortie d'un rappel abstrait de droit, est susceptible de donner lieu à un jugement préjudiciel dans le contentieux judiciaire des assurances sociales est pour le moins douteux, au regard des principes de simplicité et de rapidité que doit revêtir la procédure dans ce domaine (art. 61 lit. a LPGA; Ueli Kieser, ATSG-Kommentar, Zurich 2003, ch. 21 ss ad art. 61; pour l'ancien droit <ref-ruling>). Il peut néanmoins rester indécis pour les raisons qui suivent.
2. 2.1 Aux termes de l'art. 97 al. 1 OJ, applicable en vertu de l'art. 128 OJ, le Tribunal fédéral des assurances connaît en dernière instance des recours de droit administratif contre des décisions au sens de l'art. 5 PA. En ce qui concerne les décisions préjudicielles et les autres décisions incidentes (art. 45 PA), rendues dans une procédure précédant la décision finale, le recours de droit administratif n'est recevable - séparément d'avec le fond - que contre les décisions de cette nature qui peuvent causer un préjudice irréparable au recourant. Il faut, au surplus, conformément à l'art. 129 al. 2 en liaison avec l'art. 101 let. a OJ, que le recours de droit administratif soit également ouvert contre la décision finale (<ref-ruling> consid. 2 et les références).
Selon la jurisprudence, la notion de dommage irréparable n'est pas exactement la même dans la procédure du recours de droit administratif et dans celle du recours de droit public. Saisi d'un recours de droit administratif, le Tribunal fédéral des assurances ne juge pas de l'existence d'un dommage irréparable selon un critère unique, mais il adopte celui qui s'accorde le mieux avec la nature de la décision attaquée. En particulier, il ne se borne pas à considérer comme irréparable le seul dommage qu'une décision finale favorable au recourant ne peut pas faire disparaître complètement (<ref-ruling> consid. 4, 121 V 116 et les références).
2.2 Dans l'hypothèse où une partie aussi infime d'un contentieux en matière d'assurances sociales, ainsi que le rappel d'une institution juridique connue du droit administratif puissent faire l'objet d'une décision préjudicielle au sens de l'art. 45 al. 1 PA (supra consid. 1.2 in fine), la condition du préjudice irréparable ne serait de toute façon pas réalisée. Au vrai, on ne voit pas quel préjudice irréparable la décision litigieuse pourrait causer, si elle ne pouvait être attaquée qu'avec la décision finale (art. 45 al. 3 PA) et soumise alors seulement au contrôle du Tribunal fédéral des assurances.
Il s'ensuit que le recours de droit administratif est irrecevable.
Il s'ensuit que le recours de droit administratif est irrecevable.
3. Il appartiendra ainsi au Tribunal cantonal des assurances sociales de poursuivre avec la diligence nécessaire l'instruction de la cause et de rendre son jugement.
3. Il appartiendra ainsi au Tribunal cantonal des assurances sociales de poursuivre avec la diligence nécessaire l'instruction de la cause et de rendre son jugement.
4. Le litige ne concernant pas l'octroi ou le refus de prestations d'assurance, la procédure n'est pas gratuite (art. 134 OJ a contrario). Le recourant, qui n'obtient pas gain de cause, supportera ainsi les frais de justice (art. 156 al. 1 en corrélation avec l'art. 135 OJ).
Représenté par un avocat, D._, qui a conclu au rejet du recours, a droit à une indemnité de dépens. Dans cette mesure, sa requête d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral des assurances prononce:
Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est irrecevable.
1. Le recours est irrecevable.
2. Les frais de justice, d'un montant de 500 fr., sont mis à la charge du recourant.
2. Les frais de justice, d'un montant de 500 fr., sont mis à la charge du recourant.
3. Le recourant versera à D._ la somme de 1500 fr. (y compris la taxe à la valeur ajoutée) à titre de dépens pour l'instance fédérale.
3. Le recourant versera à D._ la somme de 1500 fr. (y compris la taxe à la valeur ajoutée) à titre de dépens pour l'instance fédérale.
4. Le présent arrêt sera communiqué aux parties, au Tribunal cantonal des assurances sociales du canton de Genève et à l'Office fédéral des assurances sociales.
Lucerne, le 10 juin 2005
Au nom du Tribunal fédéral des assurances
La Présidente de la IIIe Chambre: Le Greffier: