Sachverhalt: Sachverhalt: A. F._ (geb. 1935) wurde 1989 von U._ (geb. 1937) geschieden. 1997 verlangte er bei der Ausgleichskasse des Kantons Uri einen Auszug über die in seinen individuellen Konten gemachten Eintragungen. Auf Grund der ihm zugesandten Übersicht vom 6. November 1997 stellte er fest, dass in den Konten erst ab 1957 Einkommen aufgeführt wurden. Am 24. März 1999 reichte er der Ausgleichskasse des Kantons Uri sein Beitragsmarkenheft für Studierende der Jahre 1954 bis 1961 ein. Dieses enthält eine einzige Beitragsmarke für das Sommersemester 1956. Die übrigen für die Markierung vorgesehenen Felder wurden mit dem Vermerk "Nicht beitragspflichtig" abgestempelt. Er bat darum, ihm auf Grund "dieser zusätzlich bezahlten Beiträge den aktuellen Kontostand auszuweisen." Am 6. Oktober 1999 meldete sich F._ für eine aufgeschobene Altersrente an. Mit Schreiben vom 16.Mai 2000 teilte ihm die Ausgleichskasse des Kantons Solothurn mit, bei der Rentenberechnung habe man festgestellt, dass für das Jahr 1956 auf dem individuellen Konto keine Lohnsumme verbucht worden sei. Die Rückfragen der Ausgleichskasse des Kantons Solothurn wegen dieser Beitragslücke bei der Eidgenössischen Ausgleichskasse und der Ausgleichskasse des Kantons Bern erbrachten keine zusätzlichen Erkenntnisse. Am 29. Dezember 2002 rief F._ die aufgeschobene Altersrente per Februar 2003 ab. Mit Verfügung vom 29. Januar 2003, bestätigt mit Einspracheentscheid vom 23. Juni 2003, sprach ihm die Ausgleichskasse des Kantons Solothurn eine auf der Rentenskala 41 berechnete ordentliche Teilaltersrente zu. Am 29. Dezember 2002 rief F._ die aufgeschobene Altersrente per Februar 2003 ab. Mit Verfügung vom 29. Januar 2003, bestätigt mit Einspracheentscheid vom 23. Juni 2003, sprach ihm die Ausgleichskasse des Kantons Solothurn eine auf der Rentenskala 41 berechnete ordentliche Teilaltersrente zu. B. Die dagegen erhobene Beschwerde, mit der F._ wiederum beantragte, es sei ihm auch das Jahr 1956 als Beitragsjahr anzurechnen, wies das Versicherungsgericht des Kantons Solothurn mit Entscheid vom 22. April 2004 ab. B. Die dagegen erhobene Beschwerde, mit der F._ wiederum beantragte, es sei ihm auch das Jahr 1956 als Beitragsjahr anzurechnen, wies das Versicherungsgericht des Kantons Solothurn mit Entscheid vom 22. April 2004 ab. C. Mit Verwaltungsgerichtsbeschwerde beantragt der Versicherte erneut, es sei ihm auch das Jahr 1956 als Beitragsjahr anzuerkennen. Er habe damals an der Schule B._ studiert und dort nachgewiesen, im ersten Halbjahr 1956 AHV-Beiträge entrichtet zu haben. Vorinstanz und Verwaltung schliessen auf Abweisung der Verwaltungsgerichtsbeschwerde, während das Bundesamt für Sozialversicherung deren Gutheissung beantragt. 