ORDER
R. Brooke Jackson, United States District JudgeDana Alix Zzyym is an intersex individual.1 ECF No. 1 at ¶ 1 (Complaint). In September 2014 Dana submitted an application for a United States passport. Id. at ¶ 34. Instead of checking the box labeled “M” for male or “F” for female on the application form, - Dana instead wrote “in-tersex” below the “sex” category. ECF No. 34 at 2 (Administrative Record). By separate letter Dana informed the passport authorities that Dana was neither male nor female. Id. at 4. The letter requested “X” as an acceptable marker in the sex field to conform to International Civil Aviation Organization (“ICAO”) standards for machine-readable travel documents. ECF No. 1 at ¶ 35.
It is undisputed that in every other respect Dana is qualified to receive a passport. However, the application was denied. ECF No. 34 at 18. Dana sued, contending that the State Department’s denial of the application and its underlying binary-only gender policy violated the Administrative Procedures Act (“APA”), 5 U.S.C. § 706(2)(A), as well as plaintiffs due process and equal protection rights under the Fifth Amendment of the U.S. Constitution. See generally ECF No. 1.
Administrative Record
The Department issued its initial denial of Dana’s passport application on September 24, 2014, explaining that “[t]he Department of State currently requires the sex field on United States passports to be listed as ‘M’ or ‘F[,]’ ” and that the Department would be “unable to fulfill your request to list your sex as ‘X.’ ” ECF No. 34 at 18. The Department nevertheless stated that it would issue Dana a passport listing gender as “female,” which was the sex listed on the driver’s license plaintiff submitted to prove Dana’s identity during the application process. Id. Alternatively, the Department explained that it could issue Dana a “male” passport if Dana provided “a signed original statement on office letterhead from [Dana’s] attending medical physician” in which the doctor attested to Dana’s “new gender.” Id. at 19 (referenc*1109ing 7 FAM 1300 App. M “Gender Change”).
Dana chose neither. Instead, Dana submitted a letter to the Department on December 18, 2014 appealing the Department’s decision. Id. at 29-30. Dana included with that appeal two sworn documents by physicians from the United States Department of Veterans Affairs Medical Center in Cheyenne, Wyoming (Dana served in the Navy) that verified Dana’s sex as “intersex.”2 Id. at 31-32. Dana also met with people at the Colorado Passport Agency (part of the State Department) and informed them that Dana “did not wish a passport to be issued ... unless it could be issued showing the sex as ‘X.’ ” Id.
The Department nevertheless denied Dana’s appeal on December 29, 2014, informing Dana that the Department could not accommodate the request for the same reasons it stated in its initial denial letter. Id.) ECF No. 1 at ¶ 38. The Department, however, explained that Dana could still obtain a passport by reapplying and providing all required information on the passport application form — that is, checking either the box “M” for male or “F” for female. ECF No. 34 at 36. On February 26, 2015 Dana requested that the Department once again reconsider its decision or conduct a review hearing under 22 C.F.R. § 51.70(a). ECF No. 1 at ¶ 39. The Department denied both requests on April 10, 2015. Id. at ¶ 40.
Procedural History
Dana subsequently brought suit against defendants Secretary of State John Forbes Kerry and Sherman Portell, the Director of the Colorado Passport Agency, in their official capacities on October 25, 2015. Id. The Complaint asserts (1) that the Department’s conduct was in violation of the APA because it was “arbitrary and capricious;” (2) that the conduct also violated the APA because it exceeded the Department’s Congressionally-delegated authority; (3) that such action deprived plaintiff of due process in violation of the Fifth Amendment; (4) that it similarly deprived plaintiff of equal protection in violation of the Fifth Amendment; and (5) that the Court should issue a writ of mandamus to compel the Department to issue a passport accurately reflecting plaintiffs self-described sex. Id. at ¶¶ 48-95. Several months later on March 18, 2016 defendants filed a motion seeking judgment on the administrative record on plaintiffs APA claims and dismissal of the claims contained within the remainder of plaintiffs Complaint. ECF No. 35. The Court held oral arguments on that motion on July 20, 2016. ECF No. 51 (Transcript). That motion is the subject of this Order.3
II. STANDARD OF REVIEW
A. Motion for Judgment on the Administrative Record.
Under the APA, a court must “hold unlawful and set aside agency action, findings, and conclusions” that it finds to be, *1110among other things: (1) “arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law;” or (2) “in excess of statutory jurisdiction, authority, or limitations, or short of statutory right[.]” 5 U.S.C. § 706(2)(A), (C). I discuss each standard below.
1. “Arbitrary or Capricious” Standard.
Typically, “[a]n agency’s action is entitled to a presumption of validity, and the burden is upon the petitioner to establish the action is arbitrary or capricious.” Sorenson Commc’ns, Inc. v. F.C.C., 567 F.3d 1215, 1221 (10th Cir. 2009). Once agency action is challenged as arbitrary or capricious, a district court reviews that action under the APA as if it were an appellate court.4 See Olenhouse v. Commodity Credit Corp., 42 F.3d 1560, 1580 (10th Cir. 1994). As part of the appeal, the court “ascertain[s] whether the agency examined the relevant data and articulated a rational connection between the facts found and the decision made.” Id. at 1574 (citing Motor Vehicle Mfrs. Ass'n v. State Farm Mut. Ins. Co., 463 U.S. 29, 43, 103 S.Ct. 2856, 77 L.Ed.2d 443 (1983)). That is, the court “must determine whether the agency considered all relevant factors and whether there has been a clear error of judgment.” Id.
A court will set aside agency action “if the agency relied on factors which Congress has not intended for it to consider, entirely failed to consider an important aspect of the problem, offered an explanation for its decision that runs counter to the evidence before the agency, or is so implausible that it could not be ascribed to a difference in view or the product of agency expertise.” Id. (citing State Farm, 463 U.S. at 43, 103 S.Ct. 2856) (internal quotation marks omitted). Furthermore, “[b]ecause the arbitrary and capricious standard focuses on the rationality of an agency’s decisionmaking process rather than on the rationality of the actual decision, it is well-established that an agency’s action must be upheld, if at all, on the basis articulated by the agency itself.” Id. at 1575 (citing State Farm, 463 U.S. at 50, 103 S.Ct. 2856) (internal quotation marks and brackets omitted).
In terms of remedies, if “a court finds that an agency has acted arbitrarily in violation of the APA ... the appropriate remedy is to remand the issue back to the agency for reconsideration and, if appropriate, further investigation or an explanation adequate to support the agency’s decision upon remand.” Mohammed v. Holder, 47 F.Supp.3d 1236, 1263 (D. Colo. 2014), appeal dismissed (Nov. 19, 2014) (citing Fox Television Stations, Inc. v. F.C.C., 280 F.3d 1027, 1047 (D.C. Cir. 2002)).
2. “Excess of Authority” Standard.
Plaintiff also challenges the Department’s conduct under the APA as being in excess of its Congressionally-dele-gated authority. “Determination of whether the agency acted within the scope of its authority requires a delineation of the scope of the agency’s authority and discretion, and consideration of whether on the facts, the agency’s action can reasonably be said to be within that range.” Olenhouse, 42 F.3d at 1574 (citing Citizens to Pres. Overton Park, Inc. *1111v. Volpe, 401 U.S. 402, 415-16, 91 S.Ct. 814, 28 L.Ed.2d 136 (1971)).
B. Rule 12(b)(6) Motion to Dismiss.
To survive a 12(b)(6) motion to dismiss, the complaint must contain “enough facts to state a claim to relief that is plausible on its face.” Ridge at Red Hawk, L.L.C. v. Schneider, 493 F.3d 1174, 1177 (10th Cir. 2007) (quoting Bell Atlantic Corp. v. Twombly, 550 U.S. 544, 570, 127 S.Ct. 1955, 167 L.Ed.2d 929 (2007)). A plausible claim is a claim that “allows the court to draw the reasonable inference that the defendant is liable for the misconduct alleged.” Ashcroft v. Iqbal, 556 U.S. 662, 678, 129 S.Ct. 1937, 173 L.Ed.2d 868 (2009). While the Court must accept the well-pleaded allegations of the complaint as true and construe them in the light most favorable to the plaintiff, Robbins v. Wilkie, 300 F.3d 1208, 1210 (10th Cir. 2002), conclusory allegations are not entitled to be presumed true, Iqbal, 556 U.S. at 681, 129 S.Ct. 1937. However, so long as the plaintiff offers sufficient factual allegations such that the right to relief is raised above the speculative level, he has met the threshold pleading standard. See, e.g., Twombly, 550 U.S. at 556, 127 S.Ct. 1955; Bryson v. Gonzales, 534 F.3d 1282, 1286 (10th Cir. 2008).
III. ANALYSIS
Plaintiff seeks a passport marked “X” to comport with plaintiffs intersex identity. Citing its binary-only gender policy, the government has refused. Plaintiff contends that the government’s unwillingness to adapt to the needs and desires of intersex individuals, in contrast to policies it has implemented for others such as transsexuals, is of constitutional significance. But in my view, we are not yet at the point where this Court must venture into the constitutional fray. I find that the administrative record contains no evidence that the Department followed a rational decisionmaking process in deciding to implement its binary-only gender passport policy. Therefore, the proper next step is to remand the case to the Department to give it an opportunity either to shore up the record, if it can, or reconsider its policy; See Mohammed, 47 F.Supp.3d at 1263 (explaining that a remand is the proper remedy after a finding that an agency has acted in an “arbitrary or capricious” way).
A. The State Department’s Binary-Only Gender “Policy.”
As indicated above, because plaintiff alleges that the Department’s binary-only gender policy was not the product of reasoned decisionmaking, the Court begins by examining the administrative record for evidence that the government formulated its policy in a rational manner. Olenhouse, 42 F.3d at 1575. Before turning to that task, however, I note that plaintiff takes issue with the decisionmaking behind both the Department’s denial of plaintiffs specific passport application, as well as its underlying binary-only gender “policy.” ECF No. 1 at ¶ 50, But because the Department explains its decision to deny plaintiffs individual application by reference to its underlying policy, my focus will be on whether the Department formulated its broader policy in a rational manner.
I also note that while both parties refer to this agency action as a singular Department “policy,” doing so is a bit of a misnomer. The “policy” which the Department claims requires it to issue passports only marked “M” for male or “F” for female is really a collection of rules pertaining to gender contained within the Foreign Affairs Manual (“FAM”). See ECF No. 34 at 20-27 (citing 7 FAM 1310 Appendix M, 7 ■FAM 1320 Appendix M, 7 FAM 1330 Appendix M, 7 FAM 1340 Appendix M, 7 *1112FAM 1350 Appendix M, 7 FAM 1360 Appendix M, 7 FAM 1370 Appendix M, 7 FAM 1380 Appendix M, and 7 FAM 1390 Appendix M). These rules do not explicitly state that the Department cannot issue a passport containing an alternative gender marking. See id. Rather, they simply explain how the Department deals with different issues related to gender on passport applications. Id. The rules collectively do not contemplate the existence of a gender other than male or female. Accordingly, the Department insists that it cannot (or at least will not) issue passports that are only marked “M” or “F.”
B. The Administrative Record and the Declaration of Bennet S. Fellows.
As mentioned above, the Court begins its analysis by examining the administrar tive record. Here, however, the original record provided to the Court gave no justification for why the Department decided to institute a binary-only gender policy. Rather, it simply justified the Department’s decision to deny Dana’s application by referring to that policy. It explained that the Department requires applicants to check a box marked either “M” or “F” before it will issue a passport. Because plaintiff did not check either box, her application was denied. End of story. See generally ECF No. 34.
Perhaps recognizing this justification is no justification at all when it comes to the government’s decision to follow a binary-only gender policy, defendants supplemented the record after litigation commenced. They did so by generating and providing the Court with a declaration from Bennet S. Fellows, the Division Chief of the Office of Adjudication Policy in the Office of Adjudication of the U.S. Department of State. ECF No. 41-1.5 Nevertheless, as explained below, while this declaration gets the government somewhat closer to rationally explaining its decision to issue passports only marked “M” or “F,” it still falls short.6
First, much of Mr. Fellows’ declaration consists of background information that merely describes and clarifies the government’s policy. For instance, Mr. Fellows states that sex is one of the key data such as name, date of birth, and place of birth that the Department deems material to its adjudication of the applicant’s claim. Id. at ¶¶ 5, 13. An application without “M” or “F” checked is not considered to be complete. Id. at ¶ 6. Writing a word above “M” or “F” does not constitute submitting the *1113data required by the form. Id. at ¶¶ 6, 9. Furthermore, the Department requires visa applicants to select one of these two sex markers. Id. at ¶ 8. And similarly, no other federal agency that issues citizenship documents recognizes the use of a third marker. Id. at ¶ 15. While this is helpful background information, none of it rationalizes the decisionmaking process behind this policy.
Next, the declaration attempts to explain the government’s decision to institute its binary-only gender policy by rationalizing the policy itself. It states that key data (again sex, name, date of birth, place of birth) “must ... be supported by documentation generated by third parties, such as birth certificates, driver’s licenses, social security cards, third-party affidavits, and/or other documentation consistent with the information submitted by the applicant,” but that none of the entities issuing many of these documents “currently authorize[ ] the use of an “X” or any marker other than “M” and “F.” Id. at ¶¶ 5, 15. Thus, as the reasoning goes, the government decided to issue passports only marked “M” or “F” because the proper documentation needed to prove a passport applicant’s sex necessarily took that form.
But this rationale is unpersuasive for two reasons. First, it is entirely self-fulfilling. As Dana’s passport application experience reveals, the government rejects otherwise proper identity documents (e.g. “third-party affidavits”) when they support a sex other than male or female. See ECF No. 34 at 29-36. Thus, substance is what drives the government’s decision about what qualifies as “proper” documentation, not necessarily form. Furthermore, the Department does not even uniformly rely on these binary systems used by other jurisdictions to verify applicants’ identities. For example, although plaintiff previously obtained a driver’s license as a female, see ECF No. 34 at 7, the Department nevertheless instructed plaintiff that it would issue a passport marked “M” for male if plaintiff simply provided a physician’s letter attesting to that gender. Id. at 18-19. This is evidently the regulation the Department also follows with transgender applicants or with those whom are in the process of transitioning. Id. at 19-21.
A third rationale the declaration advances is that the applicant’s sex and photograph are among the data that are stored in a contactless chip embedded in the passport book, and that only the binary options “M” and “F” appear in these chips. Id. at ¶¶ 10,14. To the extent that is just another recitation of the Department’s current policy, it does not advance the ball. If the implication is that a decision to permit intersex individuals to write “inter-sex” or “X” on their application would require reprogramming the software and hardware that produce the chips (or the production of new forms and waste of existing supplies), then that does not explain why the government first began to require passport applicants to choose either sex in 1976, see supra note 6, but it would at least provide a reason for the Department’s reluctance to change course now. In any event, the Department hasn’t yet made that argument or attempted to show why it would consider that to be worse than accommodating this presumably small population of intersex individuals.
Fourth, the declaration stresses the importance of enabling U.S. passport information to sync with law enforcement databases that exclusively use binary gender systems. Id. at ¶ 16. Mr. Fellows candidly acknowledges, however, that “not every law enforcement record from which data is input to this system designates an individual’s sex” and states that “a field left blank in the system is assumed to reflect that the particular datum is unknown or unre*1114corded, and not to indicate ‘intersex’ or other possible alternative categorization.” Id. Nevertheless, if syncing passport information to the records contained within law enforcement databases is truly critical for the Department, then how does it rationally explain its decision to inform plaintiff that it would issue plaintiff a “male” passport knowing full well that plaintiff had state identification documents (and perhaps law enforcement database records?) listing plaintiff as “female?” See ECF No. 34 at 28. How does the Department sync a transgender individual’s passport information with law enforcement records that might list that very same passport holder as the opposite sex? Without answers to these questions, I cannot conclude that the government rationally decided to formulate a binary-only gender policy.
Finally, Mr. Fellows explains that “because only a few countries recognize a third sex marker in their issuance of passports and visas under the precatory specification of the International Civil Aviation Organization (ICAO) ... the Department’s introduction of a third gender marker in the sex field of U.S. passports could lead to inconvenience and uncertainty if U.S. citizens face difficulty entering tourist and business destinations abroad in countries that do not yet recognize a third gender marker.” Id. at ¶ 17. That raises several questions. Is this pure speculation? Is it a fact that other countries validate the information contained within a passport, as opposed to simply verifying the authenticity of the passport itself? And if a third gender marker did lead to inconvenience or difficulty entering other countries, isn’t that solely the problem of the passport holder who made the choice? The current record does not explain why these factors rationally support the policy in place.
CONCLUSION AND ORDER
I find that the administrative record, as supplemented by the Fellows declaration, does not show that the decisionmaking process that resulted in the policy in question was rational. That is not to say that it can’t be done, but the Department’s first effort to get over the arbitrary and capricious hump was not convincing. The Court remands the matter to the Department for reconsideration. The Court will not address the constitutional issues unless and until it needs to.
. Plaintiff explains: " ‘Intersex’ is an umbrella term used to describe a wide range of natural bodily variations. Intersex people are born with sex characteristics that do not fit typical binary notions of bodies designated ‘male’ or ‘female.’ In some cases, intersex traits are visible at birth, while in others they are not apparent until puberty. Some variations may not be visibly apparent at all.” Complaint, ECF No. 1, at ¶ 11.
. Dana also included a birth certificate that had been amended in 2012 to list Dana’s sex as "unknown.” ECF No. 34 at 5; ECF No. 1 at ¶ 10.
. The parties confusingly appear to suggest that plaintiff has also filed a dispositive motion in this case. See, e.g., ECF No. 45 (Plaintiff's “Reply Brief” in Support of Declaratory, Injunctive, and Other Relief). Defendants characterize plaintiffs Response to their dis-positive motion as one that "raises a distinct motion for (summary) judgment on all claims.” ECF No. 41 at 5 n.2 (emphasis in original). However, plaintiff has not formally submitted a motion for summaty judgment or any other dispositive motion in this case, aside from plaintiff’s APA "appeal” of the Department’s action discussed infra.
. As defendant explains, although in the District of Colorado a plaintiff or petitioner typically files the opening brief when "appealing” a government agency’s decision under the APA, the parties have agreed "with the Court’s approval, that defendants would file the first dispositive motion in this case," and that their motion would address the APA claims. ECF No. 35 at 6 n.l.
. Plaintiff objects to the presentation of "extra-record" material, However, the Supreme Court has instructed that when the administrative record is devoid of a justification for a challenged informal agency action, the court should “obtain from the agency, either through affidavits or testimony, such additional explanation of the reasons for the agency decision as may prove necessary.” See Camp v. Pitts, 411 U.S. 138, 142-43, 93 S.Ct. 1241, 36 L.Ed,2d 106 (1973) (per curiam); Olenhouse, 42 F.3d at 1575 (“If the agency has failed to provide a reasoned explanation for its action, or if limitations in the administrative record make it impossible to conclude the action was the product of reasoned deci-sionmaking, the reviewing court may supplement the record or remand the case to the agency for further proceedings.”). This Court's evaluation of the reasons provided in the declaration essentially moots the matter in any event.
. Mr. Fellows informs the Court that before 1976 applicants for U.S. passports were not required to identify their sex. However, since October 1976 all applicants must specify their sex as "M” or "F.” ECF No. 41-1 at ¶ 4. That of course begs the question, what was it that motivated the Department to change course in 1976? While I searched the declaration for answers and found none, this question gets at the heart of plaintiffs APA challenge — why did the government make this change and how did it go about doing so?