Faits:
A.
Dès le 16 avril 2010, les époux X._ ont pris à bail un appartement de quatre pièces dans un bâtiment d'habitation sis à Neuchâtel. La durée de la location était indéterminée. Le contrat était résiliable moyennant l'observation d'un délai de préavis de trois mois pour le 31 mars, le 30 juin ou le 30 septembre de chaque année, la première fois pour le 30 juin 2011. Le loyer et un acompte pour frais accessoires s'élevaient au total à 1'560 fr. par mois.
Le 29 août 2011, les locataires ont communiqué à la bailleresse Z._, par l'intermédiaire de sa gérance, qu'ils résiliaient le contrat avec effet au 30 septembre suivant; ils ont simultanément annoncé deux personnes qui se disaient prêtes à reprendre ensemble la location aux mêmes conditions. Ces personnes n'ont cependant pas confirmé leur candidature.
Les locataires ont déterminé une troisième personne, A._, à présenter sa candidature. Dame A._ bénéficiait de l'aide sociale; il existait par ailleurs des poursuites en cours et des actes de défaut de biens contre elle. Par lettre datée du 30 août 2011 et adressée à la gérance, le service social régional des communes de Peseux et Corcelles-Cormondrèche a fait savoir que le paiement du loyer et des charges, au montant mensuel total de 1'560 fr., serait garanti dès la signature du contrat « tant et aussi longtemps » que dame A._ dépendrait de ce service. Celui-ci prendrait en charge le premier mois; l'office de l'aide sociale de Neuchâtel « assurerait le suivi » dès le deuxième mois. Parmi diverses modalités de la garantie ainsi annoncée, le « service payeur » devrait être averti en cas de retard dans le versement du loyer; le cas échéant, les arriérés ne seraient « en aucun cas » couverts pour une période excédant trois mois.
Le 27 octobre 2011, la bailleresse a informé les locataires qu'elle n'acceptait pas la candidature de dame A._, « les renseignements obtenus sur sa personne étant défavorables ». Elle tenait les locataires pour débiteurs du loyer jusqu'à l'échéance contractuelle du 31 mars 2012, ou jusqu'à la signature d'un nouveau bail.
Les locataires ont restitué l'appartement le 31 janvier 2012; un nouveau bail, conclu entre la bailleresse et un tiers, a débuté dès le lendemain.
Afin de recouvrer les loyers et frais accessoires des mois d'octobre 2011 à janvier 2012, la bailleresse a fait notifier un commandement de payer à chacun des deux époux locataires.
B.
Le 6 mars 2012, ceux-ci ont conjointement ouvert action contre la bailleresse devant le Tribunal civil de l'arrondissement du Littoral et du Val-de-Travers. Le tribunal était requis de prononcer que les demandeurs étaient libérés de leur obligation de payer le loyer dès le 1er octobre 2011, ou, subsidiairement, dès le 15 du même mois.
La défenderesse a conclu au rejet de l'action et elle a pris des conclusions reconventionnelles. Les demandeurs devaient être condamnés à payer solidairement 6'470 fr. avec intérêts au taux de 5% par an dès le 9 février 2012; le tribunal devait donner mainlevée définitive des oppositions formées dans les deux poursuites.
Le tribunal s'est prononcé le 11 février 2013. Il a rejeté l'action principale. Accueillant l'action reconventionnelle, il a condamné les demandeurs à payer solidairement 6'240 fr. avec intérêts selon les conclusions correspondantes; à concurrence de ces prestations, le tribunal a donné mainlevée définitive des oppositions.
L'Autorité de recours en matière civile du Tribunal cantonal du canton de Neuchâtel a rejeté le recours des demandeurs par arrêt du 2 juillet 2013.
C.
Agissant principalement par la voie du recours en matière civile et subsidiairement par celle du recours constitutionnel, les demandeurs saisissent le Tribunal fédéral de conclusions semblables à celles de leur demande initiale.
La défenderesse conclut à l'irrecevabilité du recours en matière civile et au rejet du recours constitutionnel.

Considérant en droit:
1.
Dans les affaires pécuniaires civiles en matière de droit du bail à loyer, le recours ordinaire au Tribunal fédéral n'est recevable que si la valeur litigieuse s'élève à 15'000 fr. au moins (art. 74 al. 1 let. a LTF); le recours est recevable sans égard à la valeur litigieuse lorsque la contestation soulève une question juridique de principe (art. 74 al. 2 let. a LTF). En l'espèce, la valeur litigieuse est déterminée par les conclusions des demandeurs devant le Tribunal cantonal (art. 51 al. 1 let. a LTF); elle n'atteint pas le minimum légal.
Selon la jurisprudence, il y a question juridique de principe lorsque dans l'intérêt général, en particulier dans l'intérêt de la sécurité juridique, une question controversée doit être résolue par la juridiction suprême afin de parvenir à une interprétation et à une application uniforme du droit fédéral (<ref-ruling> consid. 1.1 p. 582/583; <ref-ruling> consid. 1.3 p. 4; <ref-ruling> consid. 1.2 p. 399).
Les demandeurs se prévalent de l'art. 264 al. 1 CO; ils prétendent s'être libéré de leur obligation de payer le loyer, conformément à cette disposition, en présentant une nouvelle locataire, dame A._, qui était à leur avis solvable compte tenu de la garantie de loyer accordée par le service social régional, et que la défenderesse ne pouvait pas raisonnablement refuser.
La solution du litige nécessite d'apprécier, au regard de ladite disposition, la portée de la lettre de garantie adressée à la défenderesse par le service social régional. Contrairement à l'opinion développée par les demandeurs, ce débat n'atteint pas un degré d'importance suffisant pour justifier, du point de vue de l'intérêt général, une dérogation au régime ordinaire de la valeur litigieuse minimum. Il s'ensuit que le recours en matière civile est irrecevable. Le recours constitutionnel est en revanche recevable à titre subsidiaire (art. 113 LTF). Ce recours ne peut être exercé que pour violation des droits constitutionnels (art. 116 LTF); le Tribunal fédéral ne se saisit que des griefs soulevés et motivés de façon détaillée par la partie recourante (art. 106 al. 2 et 117 LTF; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 2.2 p. 246; <ref-ruling> consid. 3.2 p. 444).
2.
Il est constant que les demandeurs se sont liés à leur adverse partie par un contrat de bail à loyer et qu'au regard des termes et du délai de résiliation convenus, leur résiliation communiquée le 29 août 2011 ne pouvait, à elle seule, pas prendre effet avant le 31 mars 2012.
A teneur de l'art. 264 al. 1 et 2 CO, lorsque le locataire restitue la chose louée sans observer les délai ou terme de congé, il n'est libéré de ses obligations envers le bailleur que s'il lui présente un nouveau locataire qui soit solvable et que le bailleur ne puisse pas raisonnablement refuser; le nouveau locataire doit en outre être disposé à reprendre le bail aux mêmes conditions (al. 1). A défaut, le locataire doit s'acquitter du loyer jusqu'à l'expiration de la durée du bail ou jusqu'au prochain terme de congé contractuel ou légal (al. 2).
Il est également constant que dame A._ n'est pas solvable, aux termes de l'art. 264 al. 1 CO, à raison de sa propre situation patrimoniale; en revanche, les demandeurs la tiennent pour solvable à raison de la lettre de garantie du service social régional. Les autres conditions d'une libération avant terme ne sont pas en cause. Ayant présenté sa candidature à l'adverse partie, les demandeurs se prétendent libérés dès le 1er octobre 2011.
3.
A l'appui du recours constitutionnel, les demandeurs invoquent la protection contre l'arbitraire conférée par l'art. 9 Cst.
Une décision est arbitraire, donc contraire à cette disposition constitutionnelle, lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou contredit d'une manière choquante le sentiment de la justice et de l'équité. Le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si sa décision apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs ou en violation d'un droit certain. En outre, il ne suffit pas que les motifs de la décision soient insoutenables; il faut encore que celle-ci soit arbitraire dans son résultat. Il ne suffit d'ailleurs pas non plus qu'une solution différente de celle retenue par l'autorité cantonale puisse être tenue pour également concevable ou apparaisse même préférable (<ref-ruling> consid. 3.2.5 p. 339; <ref-ruling> consid. 4.3 p. 319; <ref-ruling> consid. 2.4 p. 5).
4.
Selon l'argumentation développée par les demandeurs, la lettre de garantie est une déclaration de cautionnement valable au regard des art. 393 al. 1 CO et 24 de la loi neuchâteloise sur l'action sociale, du 25 juin 1996; par l'effet de cette déclaration, dame A._ doit être jugée solvable aux fins de l'application de l'art. 264 al. 1 CO.
D'après l'art. 393 al. 1 CO, une déclaration de cautionnement doit notamment contenir l'indication numérique du montant total à concurrence duquel la caution est tenue. Au regard de l'art. 392 al. 2 CO, un cautionnement peut valablement porter sur des loyers ou autres prestations périodiques qui ne deviendront exigibles que dans le futur, mais dans ce cas également, la déclaration écrite doit indiquer numériquement l'engagement total que la caution est prête à assumer. Cette indication manque en l'espèce; la lettre de garantie n'indique numériquement que le montant de l'arrérage mensuel.
La lettre ne permet d'ailleurs pas non plus d'identifier la personne morale - canton, commune, autre collectivité ou établissement public ou privé - censément obligée à titre de caution.
Il s'ensuit que les autorités précédentes n'ont certainement pas violé l'art. 9 Cst. en refusant de reconnaître à la lettre de garantie l'effet réclamé par les demandeurs. Il n'est pas nécessaire de discuter la motivation de la décision attaquée, ni d'examiner de quelle manière la candidature d'une personne certes insolvable, mais pourvue du cautionnement valable d'un tiers solvable, devrait être appréciée au regard de l'art. 264 al. 1 CO.
5.
Les demandeurs reprochent à leur adverse partie de ne les avoir pas clairement informés de ce qu'elle refusait la candidature de dame A._ en raison de son insolvabilité; ils se prétendent libérés de leur obligation en tant que la bailleresse les a laissés dans l'expectative de manière négligente et déloyale.
Par sa lettre du 27 octobre 2011, cette partie a indiqué sans aucune équivoque qu'elle n'acceptait pas la candidature de dame A._. Les demandeurs ne peuvent pas sérieusement prétendre s'être cru libérés de leur obligation encore après réception de cette communication. Compte tenu de l'attention raisonnablement exigible d'eux, ils devaient envisager que le loyer afférent à la durée résiduelle du contrat leur serait réclamé s'ils entraient en litige au sujet de cette candidature et qu'ils n'obtenaient pas gain de cause. Il leur était loisible de réclamer les explications qu'ils jugeaient éventuellement nécessaires pour tenter, ensuite, d'infléchir la décision de la bailleresse; simultanément ou exclusivement, ils pouvaient aussi lui présenter encore d'autres candidatures afin de réduire le risque encouru. Quoi qu'il en soit, les autorités précédentes n'ont de toute évidence pas appliqué arbitrairement l'art. 264 al. 1 CO.
6.
Le recours constitutionnel se révèle privé de fondement, ce qui conduit à son rejet. A titre de parties qui succombent, ses auteurs doivent acquitter l'émolument à percevoir par le Tribunal fédéral et les dépens auxquels l'adverse partie peut prétendre.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours en matière civile est irrecevable.
2.
Le recours constitutionnel est rejeté.
3.
Les demandeurs acquitteront un émolument judiciaire de 1'000 francs.
4.
Les demandeurs verseront une indemnité de 1'500 fr. à la défenderesse, solidairement entre eux, à titre de dépens.
5.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 13 janvier 2014
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente: Klett
Le greffier: Thélin