Sachverhalt:
A.
A._, geboren 1978, und B._, geboren 1981, sind syrisch-kurdischer Herkunft. Sie reisten am 23. Oktober 2002 in die Schweiz; ein Asylgesuch wurde am 10. Januar 2005 zunächst abgewiesen. In Wiedererwägung dieser Verfügung wurde ihnen jedoch am 4. November 2005 aufgrund der Mitgliedschaft von A._ bei der PKK, verbunden mit exilpolitischer Tätigkeit, die Flüchtlingseigenschaft zuerkannt, Asyl indes weiterhin verweigert, weil die aktive Mitgliedschaft in einer bewaffneten Organisation Asylunwürdigkeit zur Folge habe. A._ und B._ wurden dementsprechend als Flüchtlinge vorläufig aufgenommen.
Aufgrund der Zugehörigkeit zur Gruppe der Maktumin wurden A._ und B._ sowie ihre Kinder am 30. Mai 2013 als Staatenlose anerkannt, worauf ihnen das Amt für Migration und Zivilrecht des Kantons Graubünden die Aufenthaltsbewilligung erteilte.
B.
A._ und B._ ersuchten am 17. Juni 2013 um Erteilung der Niederlassungsbewilligung für alle Familienmitglieder. Darauf hätten sie Anspruch, weil sie sich als staatenlos anerkannte Personen seit mehr als fünf Jahren in der Schweiz aufhielten.
Das Amt für Migration und Zivilrecht des Kantons Graubünden lehnte dies jedoch am 9. Dezember 2013 ab mit der Begründung, dass die Frist von fünf Jahren erst ab der Anerkennung der Staatenlosigkeit zu laufen beginne.
Beschwerden gegen diese Verfügung wurden am 7. April 2014 vom Departement für Justiz, Sicherheit und Gesundheit sowie am 6. Oktober 2015 vom Verwaltungsgericht des Kantons Graubünden abgewiesen.
C.
A._, B._ sowie ihre drei Kinder A.B.C._, A.B.D._ und A.B.E._ haben am 8. Januar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben. Sie beantragen, den Entscheid des Verwaltungsgerichts des Kantons Graubünden vom 6. Oktober 2015 aufzuheben und ihnen die Niederlassungsbewilligung zu erteilen. Für das bundesgerichtliche Verfahren ersuchen sie um Gewährung der unentgeltlichen Rechtspflege.
Das Departement für Justiz, Sicherheit und Gesundheit und das Verwaltungsgericht des Kantons Graubünden wie auch das Staatssekretariat für Migration SEM beantragen Abweisung der Beschwerde, jeweils ohne sich ausführlich vernehmen zu lassen. In einer Stellungnahme vom 18. April 2016 beantragen die Beschwerdeführer, das Staatssekretariat für Migration zu verhalten, inhaltlich zur von ihnen dokumentierten abweichenden Praxis in anderen Kantonen und des Staatssekretariats selbst Stellung zu nehmen.

Erwägungen:
1.
Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgeschlossen gegen Entscheide, welche Bewilligungen betreffen, auf die weder das Bundesrecht noch Völkerrecht einen Anspruch einräumen (<ref-law>). Gemäss Art. 31 Abs. 1 AuG hat eine von der Schweiz als staatenlos anerkannte Person Anspruch auf Aufenthaltsbewilligung im Kanton, in dem sie sich rechtmässig aufhält. Zudem haben gemäss Art. 31 Abs. 3 AuG staatenlose Personen mit Anspruch auf eine Aufenthaltsbewilligung, die sich seit mindestens fünf Jahren rechtmässig in der Schweiz aufhalten, Anspruch auf die Niederlassungsbewilligung. Die von den Beschwerdeführern beantragte Erteilung einer Niederlassungsbewilligung beruht demnach auf einem Rechtsanspruch, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist.
Die weiteren Eintretensvoraussetzungen sind erfüllt, und auf die Beschwerde ist einzutreten.
2.
2.1. Die ausländerrechtliche Regelung des Aufenthalts von staatenlosen Personen, wie sie in Art. 31 Abs. 1 und 3 AuG vorgesehen ist, deckt sich weitgehend mit jener, welche gemäss Art. 60 des Asylgesetzes vom 26. Juni 1998 (AS 1999 2262) und zuvor schon unter der Geltung des Asylgesetzes vom 5. Oktober 1979 (Art. 26 und 28, dazu <ref-ruling> E. 2a S. 148 f.) für Flüchtlinge normiert war, denen Asyl gewährt wurde, wobei der zunächst verwendete Begriff des "ordnungsgemässen" Aufenthalts mit Änderung vom 16. Dezember 2005 (AS 2006 4745, 4752, in Kraft seit 1. Januar 2008) in Übereinstimmung mit der Regelung für Staatenlose in Art. 31 AuG durch jenen des "rechtmässigen" Aufenthalts ersetzt wurde. Mit einer weiteren Änderung vom 14. Dezember 2012 (AS 2013 4375, 4381, in Kraft seit 1. Februar 2014) strich der Gesetzgeber dann allerdings den bisherigen Anspruch auf Niederlassungsbewilligung nach fünf Jahren rechtmässigen Aufenthalts und ersetzte ihn durch die allgemeine Regelung von Art. 34 AuG, welche keinen Rechtsanspruch vermittelt. Mit einer entsprechenden Gesetzesänderung vom 25. September 2015 (BBl 2015 7181, 7207) hat der Gesetzgeber nunmehr auch Art. 31 Abs. 3 AuG gestrichen, womit der Rechtsanspruch auf Erteilung der Niederlassungsbewilligung für Staatenlose nach fünfjährigem rechtmässigem Aufenthalt entfallen wird, sobald diese Änderung in Kraft tritt, was bisher aber noch nicht geschehen ist.
2.2. Das Bundesgericht hat sich in seiner bisherigen Rechtsprechung nicht dazu aussprechen müssen, was unter "rechtmässigem" Aufenthalt von fünf Jahren im Sinne von Art. 31 Abs. 3 AuG oder auch unter dem nämlichen Begriff von aArt. 60 Abs. 2 AsylG zu verstehen ist. Hingegen war in einem Urteil vom 17. November 2010 (<ref-ruling>) zu entscheiden, welche Voraussetzungen gegeben sein müssen, damit im Sinne von Art. 63 Abs. 2 AuG ein "ordnungsgemässer" Aufenthalt von 15 Jahren vorliegt, der es nicht mehr erlaubt, eine Niederlassungsbewilligung aus bestimmten Gründen zu widerrufen. Das Bundesgericht hat dies unter Berücksichtigung der nämlichen Begriffsverwendung in anderen Bestimmungen des geltenden (Niederlassungsbewilligung nach fünf Jahren Aufenthalt der Ehegatten: Art. 42 Abs. 3 und 43 Abs. 2 AuG) oder früheren Landesrechts sowie in Niederlassungsverträgen mit anderen Staaten getan (<ref-ruling> E. 4.4 S. 13 f.). Danach gilt als ordnungsgemäss der bewilligte Aufenthalt unabhängig davon, ob dieser zu Beanstandungen Anlass gibt oder gab (<ref-ruling> E. 3b S. 367). Wenn Art. 31 Abs. 3 AuG nunmehr von rechtmässigem statt ordnungsgemässem Aufenthalt spricht, wird dieser Aspekt im Sinne der Rechtsprechung betont. Als ordnungsgemäss bzw. rechtmässig gilt bei einer anspruchsbegründenden Heirat aber auch der Aufenthalt in der Zeit zwischen Heirat und Bewilligungserteilung (<ref-ruling> E. 4.4 S. 14) oder bei einem Flüchtling die Zeit zwischen Asylgesuch und Gutheissung desselben (<ref-ruling> E. 4.6 S. 15 f.). Diese Erweiterung beruht darauf, dass auf die ausländerrechtliche Bewilligung ein Anspruch besteht und der darauf beruhende Aufenthalt als rechtmässig zu gelten hat, auch wenn das Verfahren sich unter Umständen einige Zeit dahinziehen mag. Anders verhält es sich demgegenüber für einen Aufenthalt, der aufgrund der aufschiebenden Wirkung eines Rechtsmittels lediglich toleriert wird, wenn der Ausgang des Rechtsmittels nicht dazu führt, dass dem Gesuch entsprochen wird (<ref-ruling> E. 4.4 S. 14). Analoges gilt bei Asylgesuchen: Wird das Asylgesuch schliesslich abgewiesen, ist der bisherige Aufenthalt zwar nicht illegal, denn ein Asylbewerber darf sich bis zum Abschluss des Asylverfahrens in der Schweiz aufhalten (<ref-law>), jedoch ist es nicht ein ordnungsgemässer oder rechtmässiger Aufenthalt (<ref-ruling> E. 4.6 S. 15 f.), der unter dem Gesichtspunkt von Art. 63 Abs. 2 AuG oder auch aArt. 60 Abs. 2 AsylG bedeutsam sein könnte.
2.3. Die Beschwerdeführer sind am 30. Mai 2013 als staatenlos anerkannt worden, weshalb ihnen gestützt auf Art. 31 Abs. 1 AuG die Aufenthaltsbewilligung erteilt wurde. Ihr Gesuch haben sie bereits am 21. September 2011 eingereicht, was im angefochtenen Entscheid zwar nicht festgestellt ist, aufgrund der Akten aber ergänzt werden kann (<ref-law>). Der Aufenthalt seit 21. September 2011 beruhte damit auf einem Verfahren, das in der Anerkennung einer Rechtsstellung mündete, welche Anspruch auf Aufenthaltsbewilligung gab. Ein rechtmässiger Aufenthalt von fünf Jahren im Sinne von Art. 31 Abs. 3 AuG liegt dementsprechend zwar noch nicht vor, wird aber alsbald gegeben sein.
Die Beschwerdeführer sind jedoch der Meinung, dass auch schon ihr früherer Aufenthalt als rechtmässig zu gelten habe. Sie beziehen sich jedoch zu Unrecht auf den Gegenbegriff des rechtswidrigen Aufenthalts im Sinne des Straftatbestands von Art. 115 AuG. Auch wenn für die beiden Konstellationen ein analoges Begriffspaar rechtmässig/ rechtswidrig gebildet werden mag, liegt einem Straftatbestand eine andere Wertung zugrunde als dem Erfordernis eines rechtmässigen Aufenthalts im Sinne einer ausländerrechtlichen Bewilligungskategorie. Sodann beziehen sich die Beschwerdeführer darauf, dass sie bereits vor ihrer Anerkennung als staatenlose Personen solche waren. Das ändert aber nichts daran, dass ein anspruchsbegründender Aufenthalt auf der Anerkennung bzw. wenigstens auf dem Verfahren beruht, das zur Anerkennung führt.
Man mag sich weiter die Frage stellen, ob der Aufenthalt aufgrund der Anerkennung als Flüchtling, verbunden mit der vorläufigen Aufnahme am 4. November 2005, bereits als rechtmässiger Aufenthalt im Sinne von Art. 31 Abs. 3 AuG gelten kann. Dagegen spricht jedoch, dass eine vorläufige Aufnahme die Wegweisung voraussetzt und als Ersatzmassnahme bei Undurchführbarkeit ihres Vollzugs konzipiert ist (<ref-ruling> E. 3.1 S. 308 f.). Bei Anerkennung als Flüchtling nach Massgabe der Flüchtlingskonvention (SR 0.142.30) und gleichzeitiger Verweigerung des Asyls wegen Asylunwürdigkeit im Sinne von <ref-law> mag es als eigenartig erscheinen, dass zunächst die Wegweisung ausgesprochen wird und lediglich von deren Vollzug abgesehen wird, weil dieser völkerrechtlich unzulässig ist (Art. 83 Abs. 3 AuG). Jedoch bestimmt die Flüchtlingskonvention nicht, auf welche Weise der Staat einem anerkannten Flüchtling Schutz gewährt und welche ausländerrechtliche Rechtsstellung er ihm einräumt; entscheidend ist nur, dass der Schutz effektiv ist und dem Flüchtling die Rechtsstellung zuteil wird, die ihm die Konvention garantiert. Aus der Anerkennung als Flüchtling als solche kann deshalb nicht unmittelbar abgeleitet werden, dass eine ausländerrechtliche Aufenthaltsbewilligung zu erteilen und der darauf beruhende Aufenthalt bei Art. 31 Abs. 3 AuG anzurechnen wäre.
2.4. Die Beschwerdeführer berufen sich auf ihrer Ansicht nach vergleichbare Fälle, die sie auch dokumentieren, bei denen eine Niederlassungsbewilligung erteilt worden ist. Darauf braucht nicht weiter eingegangen zu werden und auch ein diesbezüglicher Amtsbericht des Staatssekretariats ist entbehrlich, denn es ist durchaus verständlich, dass die hier erörterte Rechtslage zu unterschiedlichen Interpretationen Anlass geben konnte. Sie ist nunmehr geklärt.
3.
Die Beschwerde ist nach dem Gesagten abzuweisen. Entsprechend diesem Verfahrensausgang werden die Beschwerdeführer grundsätzlich kostenpflichtig (<ref-law>). Sie haben jedoch ein Gesuch um unentgeltliche Rechtspflege gestellt (<ref-law>). Dieses ist begründet, da die Beschwerdeführer bedürftig sind und das Rechtsbegehren nicht als aussichtslos erscheinen musste.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Den Beschwerdeführern wird die unentgeltliche Rechtspflege gewährt, und Rechtsanwalt Urs Ebnöther wird als unentgeltlicher Anwalt bestellt.
3.
Es werden keine Kosten erhoben.
4.
Rechtsanwalt Urs Ebnöther wird aus der Bundesgerichtskasse ein Honorar von Fr. 2'000 ausgerichtet.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 5. September 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass