-- ============================================================================
-- testregex.sql -- exercise pg_tre's regex engine with the AT&T regex(3)
-- conformance corpus (github/codeberg gregburd/testregex, the classic
-- Glenn Fowler / AT&T Research test suite).
--
-- This test is GENERATED by scripts/gen-testregex.py from the *.dat files
-- in that repository.  Do not edit by hand; re-run the generator to refresh.
--
-- Construction:
--   * Only ERE-flagged ('E'/'BE') rows are used (TRE compiles with
--     REG_EXTENDED).  Backreference / collating-element / word-boundary
--     rows and rows whose expectation diverges from a reference ERE engine
--     are dropped, so every embedded case has a known, engine-agnostic
--     verdict.
--   * EXACT bucket (k=0): tre_amatch(input, regex, 0) must equal the
--     corpus verdict (a position tuple => match; NOMATCH => no match).
--   * APPROX bucket (>=50% of all cases): the input of a matching row is
--     mutated by d in {1,2} random edits (insert / delete / substitute --
--     the "approximate distance phrases"), then tre_amatch(mutated, regex,
--     k) with k>=d must still match.  Anchored (^/$) patterns are excluded
--     from this bucket; they remain in the exact bucket.  Mutations come
--     from a fixed-seed RNG so this file is fully deterministic.
--
-- Totals baked into this run:
--   cases=716  exact=358  approx=358  (50.0% approx)
--   positive=341  negative=17
-- ============================================================================

CREATE EXTENSION IF NOT EXISTS pg_tre;

SET client_min_messages = 'warning';

-- The generated corpus: (regex, input, k, expect, kind).
CREATE TEMP TABLE tr_corpus(regex text, input text, k int, expect bool, kind text);
INSERT INTO tr_corpus(regex, input, k, expect, kind) VALUES
  ($x$abracadabra$$x$, $x$abracadabracadabra$x$, 0, true, 'exact'),
  ($x$a...b$x$, $x$abababbb$x$, 0, true, 'exact'),
  ($x$XXXXXX$x$, $x$..XXXXXX$x$, 0, true, 'exact'),
  ($x$\)$x$, $x$()$x$, 0, true, 'exact'),
  ($x$a]$x$, $x$a]a$x$, 0, true, 'exact'),
  ($x$\}$x$, $x$}$x$, 0, true, 'exact'),
  ($x$\]$x$, $x$]$x$, 0, true, 'exact'),
  ($x$]$x$, $x$]$x$, 0, true, 'exact'),
  ($x$^a$x$, $x$ax$x$, 0, true, 'exact'),
  ($x$\^a$x$, $x$a^a$x$, 0, true, 'exact'),
  ($x$a\^$x$, $x$a^$x$, 0, true, 'exact'),
  ($x$a$$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$a\$$x$, $x$a$$x$, 0, true, 'exact'),
  ($x$^$$x$, $x$$x$, 0, true, 'exact'),
  ($x$$^$x$, $x$$x$, 0, true, 'exact'),
  ($x$a($)$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$a*(^a)$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$(..)*(...)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$(..)*(...)*$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(bc|c)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(ab)c|abc$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a{0}b$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a*)(b?)(b+)b{3}$x$, $x$aaabbbbbbb$x$, 0, true, 'exact'),
  ($x$(a*)(b{0,1})(b{1,})b{3}$x$, $x$aaabbbbbbb$x$, 0, true, 'exact'),
  ($x$((a|a)|a)$x$, $x$a$x$, 0, true, 'exact'),
  ($x$(a*)(a|aa)$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$a*(a.|aa)$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$a(b)|c(d)|a(e)f$x$, $x$aef$x$, 0, true, 'exact'),
  ($x$(a|b)?.*$x$, $x$b$x$, 0, true, 'exact'),
  ($x$(a|b)c|a(b|c)$x$, $x$ac$x$, 0, true, 'exact'),
  ($x$(a|b)c|a(b|c)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$xc$x$, 0, true, 'exact'),
  ($x$(.a|.b).*|.*(.a|.b)$x$, $x$xa$x$, 0, true, 'exact'),
  ($x$a?(ab|ba)ab$x$, $x$abab$x$, 0, true, 'exact'),
  ($x$a?(ac{0}b|ba)ab$x$, $x$abab$x$, 0, true, 'exact'),
  ($x$ab|abab$x$, $x$abbabab$x$, 0, true, 'exact'),
  ($x$aba|bab|bba$x$, $x$baaabbbaba$x$, 0, true, 'exact'),
  ($x$aba|bab$x$, $x$baaabbbaba$x$, 0, true, 'exact'),
  ($x$(aa|aaa)*|(a|aaaaa)$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$(a.|.a.)*|(a|.a...)$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$ab|a$x$, $x$xabc$x$, 0, true, 'exact'),
  ($x$ab|a$x$, $x$xxabc$x$, 0, true, 'exact'),
  ($x$(Ab|cD)*$x$, $x$aBcD$x$, 0, true, 'exact'),
  ($x$[^-]$x$, $x$--a$x$, 0, true, 'exact'),
  ($x$[a-]*$x$, $x$--a$x$, 0, true, 'exact'),
  ($x$[a-m-]*$x$, $x$--amoma--$x$, 0, true, 'exact'),
  ($x$:1:::0:|:::1:1:0:$x$, $x$:::0:::1:::1:::0:$x$, 0, true, 'exact'),
  ($x$:1:::0:|:::1:1:1:$x$, $x$:::0:::1:::1:::0:$x$, 0, true, 'exact'),
  ($x$[[-]]$x$, $x$[[-]]$x$, 0, true, 'exact'),
  ($x$\n$x$, $x$
$x$, 0, true, 'exact'),
  ($x$[^a]$x$, $x$
$x$, 0, true, 'exact'),
  ($x$\na$x$, $x$
a$x$, 0, true, 'exact'),
  ($x$(a)(b)(c)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$xxx$x$, $x$xxx$x$, 0, true, 'exact'),
  ($x$(^|[ (,;])((([Ff]eb[^ ]* *|0*2/|\* */?)0*[6-7]))([^0-9]|$)$x$, $x$feb 6,$x$, 0, true, 'exact'),
  ($x$(^|[ (,;])((([Ff]eb[^ ]* *|0*2/|\* */?)0*[6-7]))([^0-9]|$)$x$, $x$2/7$x$, 0, true, 'exact'),
  ($x$(^|[ (,;])((([Ff]eb[^ ]* *|0*2/|\* */?)0*[6-7]))([^0-9]|$)$x$, $x$feb 1,Feb 6$x$, 0, true, 'exact'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))$x$, $x$x$x$, 0, true, 'exact'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))*$x$, $x$xx$x$, 0, true, 'exact'),
  ($x$a?(ab|ba)*$x$, $x$ababababababababababababababababababababababababababababababababababababababababa$x$, 0, true, 'exact'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$ababbabbbabbbabbbbabbbbaa$x$, 0, true, 'exact'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$ababbabbbabbbabbbbabaa$x$, 0, true, 'exact'),
  ($x$aaac|aabc|abac|abbc|baac|babc|bbac|bbbc$x$, $x$baaabbbabac$x$, 0, true, 'exact'),
  ($x$.*$x$, $x$\x01\xff$x$, 0, true, 'exact'),
  ($x$aaaa|bbbb|cccc|ddddd|eeeeee|fffffff|gggg|hhhh|iiiii|jjjjj|kkkkk|llll$x$, $x$XaaaXbbbXcccXdddXeeeXfffXgggXhhhXiiiXjjjXkkkXlllXcbaXaaaa$x$, 0, true, 'exact'),
  ($x$a*a*a*a*a*b$x$, $x$aaaaaaaaab$x$, 0, true, 'exact'),
  ($x$^$x$, $x$$x$, 0, true, 'exact'),
  ($x$$$x$, $x$$x$, 0, true, 'exact'),
  ($x$^a$$x$, $x$a$x$, 0, true, 'exact'),
  ($x$abc$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$abc$x$, $x$xabcy$x$, 0, true, 'exact'),
  ($x$abc$x$, $x$ababc$x$, 0, true, 'exact'),
  ($x$ab*c$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$ab*bc$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$ab*bc$x$, $x$abbc$x$, 0, true, 'exact'),
  ($x$ab*bc$x$, $x$abbbbc$x$, 0, true, 'exact'),
  ($x$ab+bc$x$, $x$abbc$x$, 0, true, 'exact'),
  ($x$ab+bc$x$, $x$abbbbc$x$, 0, true, 'exact'),
  ($x$ab?bc$x$, $x$abbc$x$, 0, true, 'exact'),
  ($x$ab?bc$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$ab?c$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$^abc$$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$^abc$x$, $x$abcc$x$, 0, true, 'exact'),
  ($x$abc$$x$, $x$aabc$x$, 0, true, 'exact'),
  ($x$^$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$$$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a.c$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a.c$x$, $x$axc$x$, 0, true, 'exact'),
  ($x$a.*c$x$, $x$axyzc$x$, 0, true, 'exact'),
  ($x$a[bc]d$x$, $x$abd$x$, 0, true, 'exact'),
  ($x$a[b-d]e$x$, $x$ace$x$, 0, true, 'exact'),
  ($x$a[b-d]$x$, $x$aac$x$, 0, true, 'exact'),
  ($x$a[-b]$x$, $x$a-$x$, 0, true, 'exact'),
  ($x$a[b-]$x$, $x$a-$x$, 0, true, 'exact'),
  ($x$a]$x$, $x$a]$x$, 0, true, 'exact'),
  ($x$a[]]b$x$, $x$a]b$x$, 0, true, 'exact'),
  ($x$a[^bc]d$x$, $x$aed$x$, 0, true, 'exact'),
  ($x$a[^-b]c$x$, $x$adc$x$, 0, true, 'exact'),
  ($x$a[^]b]c$x$, $x$adc$x$, 0, true, 'exact'),
  ($x$ab|cd$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$ab|cd$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a\(b$x$, $x$a(b$x$, 0, true, 'exact'),
  ($x$a\(*b$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$a\(*b$x$, $x$a((b$x$, 0, true, 'exact'),
  ($x$((a))$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a)b(c)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a+b+c$x$, $x$aabbabc$x$, 0, true, 'exact'),
  ($x$a*$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$(a*)*$x$, $x$-$x$, 0, true, 'exact'),
  ($x$(a*)+$x$, $x$-$x$, 0, true, 'exact'),
  ($x$(a*|b)*$x$, $x$-$x$, 0, true, 'exact'),
  ($x$(a+|b)*$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a+|b)+$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a+|b)?$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$[^ab]*$x$, $x$cde$x$, 0, true, 'exact'),
  ($x$(^)*$x$, $x$-$x$, 0, true, 'exact'),
  ($x$a*$x$, $x$$x$, 0, true, 'exact'),
  ($x$([abc])*d$x$, $x$abbbcd$x$, 0, true, 'exact'),
  ($x$([abc])*bcd$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a|b|c|d|e$x$, $x$e$x$, 0, true, 'exact'),
  ($x$(a|b|c|d|e)f$x$, $x$ef$x$, 0, true, 'exact'),
  ($x$((a*|b))*$x$, $x$-$x$, 0, true, 'exact'),
  ($x$abcd*efg$x$, $x$abcdefg$x$, 0, true, 'exact'),
  ($x$ab*$x$, $x$xabyabbbz$x$, 0, true, 'exact'),
  ($x$ab*$x$, $x$xayabbbz$x$, 0, true, 'exact'),
  ($x$(ab|cd)e$x$, $x$abcde$x$, 0, true, 'exact'),
  ($x$[abhgefdc]ij$x$, $x$hij$x$, 0, true, 'exact'),
  ($x$(a|b)c*d$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|ab*)bc$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a([bc]*)c*$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$a([bc]*)(c*d)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a([bc]+)(c*d)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a([bc]*)(c+d)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a[bcd]*dcdcde$x$, $x$adcdcde$x$, 0, true, 'exact'),
  ($x$(ab|a)b*c$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$((a)(b)c)(d)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$[A-Za-z_][A-Za-z0-9_]*$x$, $x$alpha$x$, 0, true, 'exact'),
  ($x$^a(bc+|b[eh])g|.h$$x$, $x$abh$x$, 0, true, 'exact'),
  ($x$(bc+d$|ef*g.|h?i(j|k))$x$, $x$effgz$x$, 0, true, 'exact'),
  ($x$(bc+d$|ef*g.|h?i(j|k))$x$, $x$ij$x$, 0, true, 'exact'),
  ($x$(bc+d$|ef*g.|h?i(j|k))$x$, $x$reffgz$x$, 0, true, 'exact'),
  ($x$(((((((((a)))))))))$x$, $x$a$x$, 0, true, 'exact'),
  ($x$multiple words$x$, $x$multiple words yeah$x$, 0, true, 'exact'),
  ($x$(.*)c(.*)$x$, $x$abcde$x$, 0, true, 'exact'),
  ($x$abcd$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a(bc)d$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$a[
-]?c$x$, $x$ac$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Qaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mo'ammar Gadhafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Kaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Qadhafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Gadafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mu'ammar Qadafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Moamar Gaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mu'ammar Qadhdhafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Khaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Ghaddafy$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Ghadafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Ghaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muamar Kaddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Quathafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Gheddafi$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Moammar Khadafy$x$, 0, true, 'exact'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Moammar Qudhafi$x$, 0, true, 'exact'),
  ($x$a+(b|c)*d+$x$, $x$aabcdd$x$, 0, true, 'exact'),
  ($x$^.+$$x$, $x$vivi$x$, 0, true, 'exact'),
  ($x$^(.+)$$x$, $x$vivi$x$, 0, true, 'exact'),
  ($x$^([^!.]+).att.com!(.+)$$x$, $x$gryphon.att.com!eby$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$$x$, $x$bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$^.+!([^!]+!)([^!]+)$$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$((foo)|(bar))!bas$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$((foo)|(bar))!bas$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$((foo)|(bar))!bas$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$((foo)|bar)!bas$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$((foo)|bar)!bas$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$((foo)|bar)!bas$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$(foo|(bar))!bas$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$(foo|(bar))!bas$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$(foo|(bar))!bas$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$(foo|bar)!bas$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$(foo|bar)!bas$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$(foo|bar)!bas$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$$x$, $x$bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$$x$, $x$foo!bar!bas$x$, 0, true, 'exact'),
  ($x$^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$$x$, $x$bas$x$, 0, true, 'exact'),
  ($x$^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$$x$, $x$bar!bas$x$, 0, true, 'exact'),
  ($x$^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$$x$, $x$foo!bas$x$, 0, true, 'exact'),
  ($x$.*(/XXX).*$x$, $x$/XXX$x$, 0, true, 'exact'),
  ($x$.*(\\XXX).*$x$, $x$\XXX$x$, 0, true, 'exact'),
  ($x$\\XXX$x$, $x$\XXX$x$, 0, true, 'exact'),
  ($x$.*(/000).*$x$, $x$/000$x$, 0, true, 'exact'),
  ($x$aa*$x$, $x$xaxaax$x$, 0, true, 'exact'),
  ($x$(a*)(ab)*(b*)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$((a*)(ab)*)((b*)(a*))$x$, $x$aba$x$, 0, true, 'exact'),
  ($x$(...?.?)*$x$, $x$xxxxxx$x$, 0, true, 'exact'),
  ($x$(a|ab)(bc|c)$x$, $x$abcabc$x$, 0, true, 'exact'),
  ($x$(aba|a*b)(aba|a*b)$x$, $x$ababa$x$, 0, true, 'exact'),
  ($x$(a*){2}$x$, $x$xxxxx$x$, 0, true, 'exact'),
  ($x$(a*)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$(a*)*$x$, $x$ax$x$, 0, true, 'exact'),
  ($x$(aba|a*b)*$x$, $x$ababa$x$, 0, true, 'exact'),
  ($x$(a(b)?)+$x$, $x$aba$x$, 0, true, 'exact'),
  ($x$(a?)((ab)?)(b?)a?(ab)?b?$x$, $x$abab$x$, 0, true, 'exact'),
  ($x$.*(.*)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a|ab)(c|bcd)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a|ab)(bcd|c)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(c|bcd)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(bcd|c)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$((a|ab)(c|bcd))(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$((a|ab)(bcd|c))(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$((ab|a)(c|bcd))(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$((ab|a)(bcd|c))(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a|ab)((c|bcd)(d*))$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a|ab)((bcd|c)(d*))$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)((c|bcd)(d*))$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)((bcd|c)(d*))$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a*)(b|abc)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a*)(abc|b)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$((a*)(b|abc))(c*)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$((a*)(abc|b))(c*)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a*)((b|abc)(c*))$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a*)((abc|b)(c*))$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a|ab)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(ab|a)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a|ab)(b*)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(ab|a)(b*)$x$, $x$ab$x$, 0, true, 'exact'),
  ($x$(a|ab)(c|bcd)(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a|ab)(bcd|c)(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(c|bcd)(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(bcd|c)(d*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a*)(b|abc)(c*)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a*)(abc|b)(c*)$x$, $x$abc$x$, 0, true, 'exact'),
  ($x$(a|ab)(c|bcd)(d|.*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a|ab)(bcd|c)(d|.*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(c|bcd)(d|.*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(ab|a)(bcd|c)(d|.*)$x$, $x$abcd$x$, 0, true, 'exact'),
  ($x$(a*)+$x$, $x$a$x$, 0, true, 'exact'),
  ($x$(a+)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$(a+)+$x$, $x$a$x$, 0, true, 'exact'),
  ($x$SAME$x$, $x$x$x$, 0, false, 'exact'),
  ($x$([a]*)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$([a]*)+$x$, $x$a$x$, 0, true, 'exact'),
  ($x$([^b]*)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$([ab]*)*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$([^a]*)*$x$, $x$b$x$, 0, true, 'exact'),
  ($x$([^ab]*)*$x$, $x$ccccxx$x$, 0, true, 'exact'),
  ($x$((z)+|a)*$x$, $x$zabcde$x$, 0, true, 'exact'),
  ($x$a+?$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$(a)$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$(a*?)$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$(a)*?$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$(a*?)*?$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$(a*)*(x)$x$, $x$x$x$, 0, true, 'exact'),
  ($x$(a*)*(x)$x$, $x$ax$x$, 0, true, 'exact'),
  ($x$(a*)*(x)$x$, $x$axa$x$, 0, true, 'exact'),
  ($x$(a*)+(x)$x$, $x$x$x$, 0, true, 'exact'),
  ($x$(a*)+(x)$x$, $x$ax$x$, 0, true, 'exact'),
  ($x$(a*)+(x)$x$, $x$axa$x$, 0, true, 'exact'),
  ($x$(a*){2}(x)$x$, $x$x$x$, 0, true, 'exact'),
  ($x$(a*){2}(x)$x$, $x$ax$x$, 0, true, 'exact'),
  ($x$(a*){2}(x)$x$, $x$axa$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$$x$, 0, false, 'exact'),
  ($x$((..)|(.))*$x$, $x$$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$a$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$a$x$, 0, false, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$a$x$, 0, false, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$a$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$a$x$, 0, false, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$a$x$, 0, false, 'exact'),
  ($x$((..)|(.))*$x$, $x$a$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aa$x$, 0, false, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$aa$x$, 0, false, 'exact'),
  ($x$((..)|(.))*$x$, $x$aa$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))*$x$, $x$aaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))*$x$, $x$aaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))*$x$, $x$aaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){1}$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){2}$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.)){3}$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$((..)|(.))*$x$, $x$aaaaaa$x$, 0, true, 'exact'),
  ($x$X(.?){0,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){1,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){2,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){3,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){4,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){5,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){6,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){7,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){8,}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){0,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){1,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){2,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){3,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){4,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){5,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){6,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){7,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$X(.?){8,8}Y$x$, $x$X1234567Y$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){0,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){1,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){2,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){3,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){4,}(d*)$x$, $x$ababcd$x$, 0, false, 'exact'),
  ($x$(a|ab|c|bcd){0,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){1,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){2,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){3,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd){4,10}(d*)$x$, $x$ababcd$x$, 0, false, 'exact'),
  ($x$(a|ab|c|bcd)*(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(a|ab|c|bcd)+(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){0,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){1,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){2,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){3,}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){4,}(d*)$x$, $x$ababcd$x$, 0, false, 'exact'),
  ($x$(ab|a|c|bcd){0,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){1,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){2,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){3,10}(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd){4,10}(d*)$x$, $x$ababcd$x$, 0, false, 'exact'),
  ($x$(ab|a|c|bcd)*(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$(ab|a|c|bcd)+(d*)$x$, $x$ababcd$x$, 0, true, 'exact'),
  ($x$a...b$x$, $x$abababhbb$x$, 1, true, 'approx'),
  ($x$XXXXXX$x$, $x$..buXXXXXX$x$, 2, true, 'approx'),
  ($x$\)$x$, $x$$x$, 2, true, 'approx'),
  ($x$a]$x$, $x$uwa]a$x$, 2, true, 'approx'),
  ($x$\}$x$, $x$c}$x$, 2, true, 'approx'),
  ($x$\]$x$, $x$$x$, 1, true, 'approx'),
  ($x$]$x$, $x$r$x$, 2, true, 'approx'),
  ($x$(..)*(...)*$x$, $x$fo$x$, 2, true, 'approx'),
  ($x$(..)*(...)*$x$, $x$avd$x$, 2, true, 'approx'),
  ($x$(ab|a)(bc|c)$x$, $x$abv$x$, 2, true, 'approx'),
  ($x$(ab)c|abc$x$, $x$abc$x$, 1, true, 'approx'),
  ($x$a{0}b$x$, $x$b$x$, 1, true, 'approx'),
  ($x$(a*)(b?)(b+)b{3}$x$, $x$aabbbbbbb$x$, 1, true, 'approx'),
  ($x$(a*)(b{0,1})(b{1,})b{3}$x$, $x$aaapbbbbbj$x$, 2, true, 'approx'),
  ($x$((a|a)|a)$x$, $x$n$x$, 2, true, 'approx'),
  ($x$(a*)(a|aa)$x$, $x$aaa$x$, 2, true, 'approx'),
  ($x$a*(a.|aa)$x$, $x$aaaau$x$, 2, true, 'approx'),
  ($x$a(b)|c(d)|a(e)f$x$, $x$a$x$, 2, true, 'approx'),
  ($x$(a|b)?.*$x$, $x$eb$x$, 2, true, 'approx'),
  ($x$(a|b)c|a(b|c)$x$, $x$$x$, 2, true, 'approx'),
  ($x$(a|b)c|a(b|c)$x$, $x$a$x$, 2, true, 'approx'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$b$x$, 2, true, 'approx'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$d$x$, 2, true, 'approx'),
  ($x$(.a|.b).*|.*(.a|.b)$x$, $x$td$x$, 2, true, 'approx'),
  ($x$a?(ab|ba)ab$x$, $x$abath$x$, 2, true, 'approx'),
  ($x$a?(ac{0}b|ba)ab$x$, $x$abat$x$, 2, true, 'approx'),
  ($x$ab|abab$x$, $x$abkaba$x$, 2, true, 'approx'),
  ($x$aba|bab|bba$x$, $x$baaabbbuba$x$, 1, true, 'approx'),
  ($x$aba|bab$x$, $x$faaabbbaba$x$, 1, true, 'approx'),
  ($x$(aa|aaa)*|(a|aaaaa)$x$, $x$av$x$, 1, true, 'approx'),
  ($x$(a.|.a.)*|(a|.a...)$x$, $x$aay$x$, 2, true, 'approx'),
  ($x$ab|a$x$, $x$xab$x$, 1, true, 'approx'),
  ($x$ab|a$x$, $x$xxabe$x$, 1, true, 'approx'),
  ($x$(Ab|cD)*$x$, $x$aecD$x$, 2, true, 'approx'),
  ($x$[a-]*$x$, $x$aa$x$, 2, true, 'approx'),
  ($x$[a-m-]*$x$, $x$--amoea-p$x$, 2, true, 'approx'),
  ($x$:1:::0:|:::1:1:0:$x$, $x$t:l:0:::1:::1:::0:$x$, 2, true, 'approx'),
  ($x$:1:::0:|:::1:1:1:$x$, $x$:::0:::1:p::1:::0:$x$, 1, true, 'approx'),
  ($x$[[-]]$x$, $x$[[-p]$x$, 2, true, 'approx'),
  ($x$\n$x$, $x$y$x$, 2, true, 'approx'),
  ($x$\na$x$, $x$
a$x$, 1, true, 'approx'),
  ($x$(a)(b)(c)$x$, $x$aejc$x$, 2, true, 'approx'),
  ($x$xxx$x$, $x$hxx$x$, 1, true, 'approx'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))$x$, $x$dx$x$, 1, true, 'approx'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))*$x$, $x$bx$x$, 2, true, 'approx'),
  ($x$a?(ab|ba)*$x$, $x$ababababababababababababababababaoabababababababababababababababababababababababa$x$, 1, true, 'approx'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$ababbabbbabbbabbbbalbbbaa$x$, 1, true, 'approx'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$ababbabbbabbbabbbabaa$x$, 1, true, 'approx'),
  ($x$aaac|aabc|abac|abbc|baac|babc|bbac|bbbc$x$, $x$baaaabbbabac$x$, 2, true, 'approx'),
  ($x$.*$x$, $x$\x1\xff$x$, 1, true, 'approx'),
  ($x$aaaa|bbbb|cccc|ddddd|eeeeee|fffffff|gggg|hhhh|iiiii|jjjjj|kkkkk|llll$x$, $x$XaarXbbbXcccXdddXeeeXfffXgggXhhhXiiiXjjjXkkkXlllXcbaXaaaa$x$, 2, true, 'approx'),
  ($x$a*a*a*a*a*b$x$, $x$aavaaaaaaab$x$, 2, true, 'approx'),
  ($x$abc$x$, $x$aabc$x$, 2, true, 'approx'),
  ($x$abc$x$, $x$xuabsy$x$, 2, true, 'approx'),
  ($x$abc$x$, $x$aebbc$x$, 2, true, 'approx'),
  ($x$ab*c$x$, $x$aedc$x$, 2, true, 'approx'),
  ($x$ab*bc$x$, $x$hbc$x$, 2, true, 'approx'),
  ($x$ab*bc$x$, $x$arbc$x$, 1, true, 'approx'),
  ($x$ab*bc$x$, $x$abbbbc$x$, 1, true, 'approx'),
  ($x$ab+bc$x$, $x$avbc$x$, 2, true, 'approx'),
  ($x$ab+bc$x$, $x$abbbc$x$, 1, true, 'approx'),
  ($x$ab?bc$x$, $x$abc$x$, 1, true, 'approx'),
  ($x$ab?bc$x$, $x$acc$x$, 2, true, 'approx'),
  ($x$ab?c$x$, $x$abcf$x$, 1, true, 'approx'),
  ($x$a.c$x$, $x$acyc$x$, 2, true, 'approx'),
  ($x$a.c$x$, $x$afc$x$, 1, true, 'approx'),
  ($x$a.*c$x$, $x$axzyzc$x$, 2, true, 'approx'),
  ($x$a[bc]d$x$, $x$xabtd$x$, 2, true, 'approx'),
  ($x$a[b-d]e$x$, $x$acr$x$, 2, true, 'approx'),
  ($x$a[b-d]$x$, $x$baau$x$, 2, true, 'approx'),
  ($x$a[-b]$x$, $x$$x$, 2, true, 'approx'),
  ($x$a[b-]$x$, $x$t-$x$, 1, true, 'approx'),
  ($x$a]$x$, $x$]s$x$, 2, true, 'approx'),
  ($x$a[]]b$x$, $x$awb$x$, 1, true, 'approx'),
  ($x$ab|cd$x$, $x$auc$x$, 2, true, 'approx'),
  ($x$ab|cd$x$, $x$ambcd$x$, 1, true, 'approx'),
  ($x$a\(b$x$, $x$b$x$, 2, true, 'approx'),
  ($x$a\(*b$x$, $x$eab$x$, 1, true, 'approx'),
  ($x$a\(*b$x$, $x$azr((b$x$, 2, true, 'approx'),
  ($x$((a))$x$, $x$bc$x$, 1, true, 'approx'),
  ($x$(a)b(c)$x$, $x$abci$x$, 2, true, 'approx'),
  ($x$a+b+c$x$, $x$akabbabc$x$, 2, true, 'approx'),
  ($x$a*$x$, $x$a$x$, 2, true, 'approx'),
  ($x$(a*)*$x$, $x$z$x$, 2, true, 'approx'),
  ($x$(a*)+$x$, $x$$x$, 1, true, 'approx'),
  ($x$(a*|b)*$x$, $x$$x$, 2, true, 'approx'),
  ($x$(a+|b)*$x$, $x$ahbj$x$, 2, true, 'approx'),
  ($x$(a+|b)+$x$, $x$a$x$, 1, true, 'approx'),
  ($x$(a+|b)?$x$, $x$azb$x$, 2, true, 'approx'),
  ($x$a*$x$, $x$p$x$, 2, true, 'approx'),
  ($x$([abc])*d$x$, $x$abbcd$x$, 2, true, 'approx'),
  ($x$([abc])*bcd$x$, $x$xlabcd$x$, 2, true, 'approx'),
  ($x$a|b|c|d|e$x$, $x$oh$x$, 2, true, 'approx'),
  ($x$(a|b|c|d|e)f$x$, $x$eka$x$, 2, true, 'approx'),
  ($x$((a*|b))*$x$, $x$$x$, 2, true, 'approx'),
  ($x$abcd*efg$x$, $x$aywcdefg$x$, 2, true, 'approx'),
  ($x$ab*$x$, $x$xabucyabbbz$x$, 2, true, 'approx'),
  ($x$ab*$x$, $x$xayabbz$x$, 2, true, 'approx'),
  ($x$(ab|cd)e$x$, $x$cde$x$, 2, true, 'approx'),
  ($x$[abhgefdc]ij$x$, $x$rhij$x$, 1, true, 'approx'),
  ($x$(a|b)c*d$x$, $x$aibycd$x$, 2, true, 'approx'),
  ($x$(ab|ab*)bc$x$, $x$vmabc$x$, 2, true, 'approx'),
  ($x$a([bc]*)c*$x$, $x$eabc$x$, 1, true, 'approx'),
  ($x$a([bc]*)(c*d)$x$, $x$abc$x$, 2, true, 'approx'),
  ($x$a([bc]+)(c*d)$x$, $x$bcd$x$, 2, true, 'approx'),
  ($x$a([bc]*)(c+d)$x$, $x$ambcd$x$, 2, true, 'approx'),
  ($x$a[bcd]*dcdcde$x$, $x$mdcdcde$x$, 2, true, 'approx'),
  ($x$(ab|a)b*c$x$, $x$bc$x$, 2, true, 'approx'),
  ($x$((a)(b)c)(d)$x$, $x$abc$x$, 2, true, 'approx'),
  ($x$[A-Za-z_][A-Za-z0-9_]*$x$, $x$alxphn$x$, 2, true, 'approx'),
  ($x$(((((((((a)))))))))$x$, $x$$x$, 1, true, 'approx'),
  ($x$multiple words$x$, $x$multipale words yeah$x$, 2, true, 'approx'),
  ($x$(.*)c(.*)$x$, $x$abche$x$, 2, true, 'approx'),
  ($x$abcd$x$, $x$alcd$x$, 2, true, 'approx'),
  ($x$a(bc)d$x$, $x$abchd$x$, 2, true, 'approx'),
  ($x$a[
-]?c$x$, $x$x$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Qaddaf$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mo'ammao Godhafi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar bKaddafi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammr Qadhafi$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$mMuammar Gaadafi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mu'amar Qadafi$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Moamaj Gaddafi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mu'ammar adhdhafu$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Khadafi$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muamar Ghhaddafy$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar haafi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Ghaddaf$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muamr Kaddafi$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammaor Quathafi$x$, 1, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Muammar Gheddapi$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Moammwar Khadafy$x$, 2, true, 'approx'),
  ($x$M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]$x$, $x$Mammar Qudhafi$x$, 2, true, 'approx'),
  ($x$a+(b|c)*d+$x$, $x$aabdd$x$, 2, true, 'approx'),
  ($x$((foo)|(bar))!bas$x$, $x$baue!bas$x$, 2, true, 'approx'),
  ($x$((foo)|(bar))!bas$x$, $x$oo!bar!bas$x$, 2, true, 'approx'),
  ($x$((foo)|(bar))!bas$x$, $x$foobas$x$, 2, true, 'approx'),
  ($x$((foo)|bar)!bas$x$, $x$bar!basq$x$, 2, true, 'approx'),
  ($x$((foo)|bar)!bas$x$, $x$noo!bar!bas$x$, 2, true, 'approx'),
  ($x$((foo)|bar)!bas$x$, $x$uoo!as$x$, 2, true, 'approx'),
  ($x$(foo|(bar))!bas$x$, $x$barybas$x$, 1, true, 'approx'),
  ($x$(foo|(bar))!bas$x$, $x$foo!bdr!ba$x$, 2, true, 'approx'),
  ($x$(foo|(bar))!bas$x$, $x$foobas$x$, 1, true, 'approx'),
  ($x$(foo|bar)!bas$x$, $x$bar!bus$x$, 2, true, 'approx'),
  ($x$(foo|bar)!bas$x$, $x$foo!bafrd!bas$x$, 2, true, 'approx'),
  ($x$(foo|bar)!bas$x$, $x$fooebay$x$, 2, true, 'approx'),
  ($x$.*(/XXX).*$x$, $x$yoXXX$x$, 2, true, 'approx'),
  ($x$.*(\\XXX).*$x$, $x$\XX$x$, 1, true, 'approx'),
  ($x$\\XXX$x$, $x$i\XXX$x$, 1, true, 'approx'),
  ($x$.*(/000).*$x$, $x$00$x$, 2, true, 'approx'),
  ($x$aa*$x$, $x$oxauaax$x$, 2, true, 'approx'),
  ($x$(a*)(ab)*(b*)$x$, $x$lbc$x$, 2, true, 'approx'),
  ($x$((a*)(ab)*)((b*)(a*))$x$, $x$qa$x$, 2, true, 'approx'),
  ($x$(...?.?)*$x$, $x$xxxxdx$x$, 2, true, 'approx'),
  ($x$(a|ab)(bc|c)$x$, $x$arcatc$x$, 2, true, 'approx'),
  ($x$(aba|a*b)(aba|a*b)$x$, $x$anbaa$x$, 2, true, 'approx'),
  ($x$(a*){2}$x$, $x$sxxxx$x$, 2, true, 'approx'),
  ($x$(a*)*$x$, $x$ma$x$, 1, true, 'approx'),
  ($x$(a*)*$x$, $x$axb$x$, 1, true, 'approx'),
  ($x$(aba|a*b)*$x$, $x$ababa$x$, 2, true, 'approx'),
  ($x$(a(b)?)+$x$, $x$aqa$x$, 2, true, 'approx'),
  ($x$(a?)((ab)?)(b?)a?(ab)?b?$x$, $x$asab$x$, 2, true, 'approx'),
  ($x$.*(.*)$x$, $x$as$x$, 2, true, 'approx'),
  ($x$(a|ab)(c|bcd)$x$, $x$bbd$x$, 2, true, 'approx'),
  ($x$(a|ab)(bcd|c)$x$, $x$bcdo$x$, 2, true, 'approx'),
  ($x$(ab|a)(c|bcd)$x$, $x$abd$x$, 1, true, 'approx'),
  ($x$(ab|a)(bcd|c)$x$, $x$abds$x$, 2, true, 'approx'),
  ($x$((a|ab)(c|bcd))(d*)$x$, $x$abrcd$x$, 2, true, 'approx'),
  ($x$((a|ab)(bcd|c))(d*)$x$, $x$kbcmd$x$, 2, true, 'approx'),
  ($x$((ab|a)(c|bcd))(d*)$x$, $x$dbcd$x$, 1, true, 'approx'),
  ($x$((ab|a)(bcd|c))(d*)$x$, $x$abc$x$, 1, true, 'approx'),
  ($x$(a|ab)((c|bcd)(d*))$x$, $x$bd$x$, 2, true, 'approx'),
  ($x$(a|ab)((bcd|c)(d*))$x$, $x$wbabcd$x$, 2, true, 'approx'),
  ($x$(ab|a)((c|bcd)(d*))$x$, $x$ahcd$x$, 1, true, 'approx'),
  ($x$(ab|a)((bcd|c)(d*))$x$, $x$cabc$x$, 2, true, 'approx'),
  ($x$(a*)(b|abc)$x$, $x$pabc$x$, 2, true, 'approx'),
  ($x$(a*)(abc|b)$x$, $x$hmc$x$, 2, true, 'approx'),
  ($x$((a*)(b|abc))(c*)$x$, $x$aboc$x$, 2, true, 'approx'),
  ($x$((a*)(abc|b))(c*)$x$, $x$arbc$x$, 1, true, 'approx'),
  ($x$(a*)((b|abc)(c*))$x$, $x$bc$x$, 1, true, 'approx'),
  ($x$(a*)((abc|b)(c*))$x$, $x$qb$x$, 2, true, 'approx'),
  ($x$(a|ab)$x$, $x$iob$x$, 2, true, 'approx'),
  ($x$(ab|a)$x$, $x$b$x$, 1, true, 'approx'),
  ($x$(a|ab)(b*)$x$, $x$a$x$, 1, true, 'approx'),
  ($x$(ab|a)(b*)$x$, $x$abdh$x$, 2, true, 'approx'),
  ($x$(a|ab)(c|bcd)(d*)$x$, $x$aboo$x$, 2, true, 'approx'),
  ($x$(a|ab)(bcd|c)(d*)$x$, $x$bid$x$, 2, true, 'approx'),
  ($x$(ab|a)(c|bcd)(d*)$x$, $x$kabcd$x$, 1, true, 'approx'),
  ($x$(ab|a)(bcd|c)(d*)$x$, $x$abnd$x$, 2, true, 'approx'),
  ($x$(a*)(b|abc)(c*)$x$, $x$ibc$x$, 1, true, 'approx'),
  ($x$(a*)(abc|b)(c*)$x$, $x$arzc$x$, 2, true, 'approx'),
  ($x$(a|ab)(c|bcd)(d|.*)$x$, $x$ebc$x$, 2, true, 'approx'),
  ($x$(a|ab)(bcd|c)(d|.*)$x$, $x$abck$x$, 1, true, 'approx'),
  ($x$(ab|a)(c|bcd)(d|.*)$x$, $x$abcdb$x$, 1, true, 'approx'),
  ($x$(ab|a)(bcd|c)(d|.*)$x$, $x$pbcdz$x$, 2, true, 'approx'),
  ($x$(a*)+$x$, $x$$x$, 2, true, 'approx'),
  ($x$(a+)*$x$, $x$ds$x$, 2, true, 'approx'),
  ($x$(a+)+$x$, $x$$x$, 2, true, 'approx'),
  ($x$([a]*)*$x$, $x$$x$, 2, true, 'approx'),
  ($x$([a]*)+$x$, $x$n$x$, 2, true, 'approx'),
  ($x$([ab]*)*$x$, $x$e$x$, 2, true, 'approx'),
  ($x$((z)+|a)*$x$, $x$zakbcde$x$, 1, true, 'approx'),
  ($x$a+?$x$, $x$uaaaaaa$x$, 1, true, 'approx'),
  ($x$(a)$x$, $x$aama$x$, 2, true, 'approx'),
  ($x$(a*?)$x$, $x$lka$x$, 2, true, 'approx'),
  ($x$(a)*?$x$, $x$hra$x$, 2, true, 'approx'),
  ($x$(a*?)*?$x$, $x$aa$x$, 2, true, 'approx'),
  ($x$(a*)*(x)$x$, $x$k$x$, 2, true, 'approx'),
  ($x$(a*)*(x)$x$, $x$n$x$, 2, true, 'approx'),
  ($x$(a*)*(x)$x$, $x$xja$x$, 2, true, 'approx'),
  ($x$(a*)+(x)$x$, $x$$x$, 2, true, 'approx'),
  ($x$(a*)+(x)$x$, $x$af$x$, 2, true, 'approx'),
  ($x$(a*)+(x)$x$, $x$nxa$x$, 2, true, 'approx'),
  ($x$(a*){2}(x)$x$, $x$v$x$, 2, true, 'approx'),
  ($x$(a*){2}(x)$x$, $x$a$x$, 2, true, 'approx'),
  ($x$(a*){2}(x)$x$, $x$aa$x$, 1, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$$x$, 2, true, 'approx'),
  ($x$((..)|(.))$x$, $x$t$x$, 2, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$m$x$, 1, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$ag$x$, 1, true, 'approx'),
  ($x$((..)|(.))$x$, $x$ad$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$aw$x$, 2, true, 'approx'),
  ($x$((..)|(.)){2}$x$, $x$a$x$, 2, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$aao$x$, 2, true, 'approx'),
  ($x$((..)|(.))$x$, $x$zaaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))$x$, $x$ama$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$a$x$, 2, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$aaza$x$, 1, true, 'approx'),
  ($x$((..)|(.)){2}$x$, $x$aab$x$, 2, true, 'approx'),
  ($x$((..)|(.)){3}$x$, $x$paah$x$, 2, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$aaw$x$, 2, true, 'approx'),
  ($x$((..)|(.))$x$, $x$aaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))$x$, $x$laasa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$auaa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$ahzaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){2}$x$, $x$gaaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.)){3}$x$, $x$saaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$vaaad$x$, 2, true, 'approx'),
  ($x$((..)|(.))$x$, $x$aayoaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))$x$, $x$aaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$yaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$aaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.)){2}$x$, $x$aaeawa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){3}$x$, $x$aaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$aaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.))$x$, $x$adaqaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.))((..)|(.))$x$, $x$abaaaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.))((..)|(.))((..)|(.))$x$, $x$aaaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.)){1}$x$, $x$aaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){2}$x$, $x$aaaaa$x$, 2, true, 'approx'),
  ($x$((..)|(.)){3}$x$, $x$aaaaaaa$x$, 1, true, 'approx'),
  ($x$((..)|(.))*$x$, $x$asagaaaa$x$, 2, true, 'approx'),
  ($x$X(.?){0,}Y$x$, $x$X123467Y$x$, 1, true, 'approx'),
  ($x$X(.?){1,}Y$x$, $x$Xkk234567Y$x$, 2, true, 'approx'),
  ($x$X(.?){2,}Y$x$, $x$X13467Y$x$, 2, true, 'approx'),
  ($x$X(.?){3,}Y$x$, $x$X12345n67Y$x$, 2, true, 'approx'),
  ($x$X(.?){4,}Y$x$, $x$r1234o567Y$x$, 2, true, 'approx'),
  ($x$X(.?){5,}Y$x$, $x$X1n34567Y$x$, 2, true, 'approx'),
  ($x$X(.?){6,}Y$x$, $x$X12m4567Y$x$, 1, true, 'approx'),
  ($x$X(.?){7,}Y$x$, $x$X123457Y$x$, 1, true, 'approx'),
  ($x$X(.?){8,}Y$x$, $x$X1q234567Y$x$, 1, true, 'approx'),
  ($x$X(.?){0,8}Y$x$, $x$m123567Y$x$, 2, true, 'approx'),
  ($x$X(.?){1,8}Y$x$, $x$X123456b7Y$x$, 1, true, 'approx'),
  ($x$X(.?){2,8}Y$x$, $x$X1c34567Y$x$, 1, true, 'approx'),
  ($x$X(.?){3,8}Y$x$, $x$1234567Y$x$, 2, true, 'approx'),
  ($x$X(.?){4,8}Y$x$, $x$X123457Yb$x$, 2, true, 'approx'),
  ($x$X(.?){5,8}Y$x$, $x$Xq234567Y$x$, 2, true, 'approx'),
  ($x$X(.?){6,8}Y$x$, $x$X123z5r7Y$x$, 2, true, 'approx'),
  ($x$X(.?){7,8}Y$x$, $x$Xzy234567Y$x$, 2, true, 'approx'),
  ($x$X(.?){8,8}Y$x$, $x$X1234567dY$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd){0,}(d*)$x$, $x$ababfd$x$, 1, true, 'approx'),
  ($x$(a|ab|c|bcd){1,}(d*)$x$, $x$ababc$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd){2,}(d*)$x$, $x$aybbcd$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd){3,}(d*)$x$, $x$axbabbcd$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd){0,10}(d*)$x$, $x$tfbabcd$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd){1,10}(d*)$x$, $x$abacd$x$, 1, true, 'approx'),
  ($x$(a|ab|c|bcd){2,10}(d*)$x$, $x$ababcd$x$, 1, true, 'approx'),
  ($x$(a|ab|c|bcd){3,10}(d*)$x$, $x$aqbqabcd$x$, 2, true, 'approx'),
  ($x$(a|ab|c|bcd)*(d*)$x$, $x$abubcd$x$, 1, true, 'approx'),
  ($x$(a|ab|c|bcd)+(d*)$x$, $x$babcd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){0,}(d*)$x$, $x$abbbcd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){1,}(d*)$x$, $x$abacd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){2,}(d*)$x$, $x$abfbcd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){3,}(d*)$x$, $x$abjbvcd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){0,10}(d*)$x$, $x$abqabcg$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){1,10}(d*)$x$, $x$ababacd$x$, 1, true, 'approx'),
  ($x$(ab|a|c|bcd){2,10}(d*)$x$, $x$aabcd$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd){3,10}(d*)$x$, $x$ababch$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd)*(d*)$x$, $x$ababcdc$x$, 2, true, 'approx'),
  ($x$(ab|a|c|bcd)+(d*)$x$, $x$ababvcd$x$, 1, true, 'approx'),
  ($x$a...b$x$, $x$abababbkb$x$, 1, true, 'approx'),
  ($x$XXXXXX$x$, $x$..XXXneXX$x$, 2, true, 'approx'),
  ($x$\)$x$, $x$i)z$x$, 2, true, 'approx'),
  ($x$a]$x$, $x$g]$x$, 2, true, 'approx'),
  ($x$\}$x$, $x$au$x$, 2, true, 'approx'),
  ($x$\]$x$, $x$]p$x$, 1, true, 'approx'),
  ($x$]$x$, $x$wu$x$, 2, true, 'approx'),
  ($x$(..)*(...)*$x$, $x$d$x$, 2, true, 'approx'),
  ($x$(..)*(...)*$x$, $x$abcdq$x$, 1, true, 'approx'),
  ($x$(ab|a)(bc|c)$x$, $x$ae$x$, 2, true, 'approx'),
  ($x$(ab)c|abc$x$, $x$am$x$, 2, true, 'approx'),
  ($x$a{0}b$x$, $x$aob$x$, 2, true, 'approx'),
  ($x$(a*)(b?)(b+)b{3}$x$, $x$aaabmbbbbbjb$x$, 2, true, 'approx'),
  ($x$(a*)(b{0,1})(b{1,})b{3}$x$, $x$aaabbbbbb$x$, 1, true, 'approx'),
  ($x$((a|a)|a)$x$, $x$za$x$, 2, true, 'approx'),
  ($x$(a*)(a|aa)$x$, $x$aala$x$, 2, true, 'approx'),
  ($x$a*(a.|aa)$x$, $x$aaaaq$x$, 1, true, 'approx'),
  ($x$a(b)|c(d)|a(e)f$x$, $x$af$x$, 2, true, 'approx'),
  ($x$(a|b)?.*$x$, $x$ibq$x$, 2, true, 'approx'),
  ($x$(a|b)c|a(b|c)$x$, $x$e$x$, 2, true, 'approx'),
  ($x$(a|b)c|a(b|c)$x$, $x$b$x$, 1, true, 'approx'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$ablc$x$, 1, true, 'approx'),
  ($x$(a|b)*c|(a|ab)*c$x$, $x$c$x$, 2, true, 'approx'),
  ($x$(.a|.b).*|.*(.a|.b)$x$, $x$t$x$, 2, true, 'approx'),
  ($x$a?(ab|ba)ab$x$, $x$ababd$x$, 2, true, 'approx'),
  ($x$a?(ac{0}b|ba)ab$x$, $x$bag$x$, 2, true, 'approx'),
  ($x$ab|abab$x$, $x$abbabab$x$, 2, true, 'approx'),
  ($x$aba|bab|bba$x$, $x$baabbbabq$x$, 2, true, 'approx'),
  ($x$aba|bab$x$, $x$baavabbbaba$x$, 1, true, 'approx'),
  ($x$(aa|aaa)*|(a|aaaaa)$x$, $x$apa$x$, 1, true, 'approx'),
  ($x$(a.|.a.)*|(a|.a...)$x$, $x$a$x$, 2, true, 'approx'),
  ($x$ab|a$x$, $x$xgac$x$, 2, true, 'approx'),
  ($x$ab|a$x$, $x$xxbc$x$, 1, true, 'approx'),
  ($x$(Ab|cD)*$x$, $x$BcDn$x$, 2, true, 'approx'),
  ($x$[a-]*$x$, $x$-a$x$, 2, true, 'approx'),
  ($x$[a-m-]*$x$, $x$l-amoma--$x$, 2, true, 'approx'),
  ($x$:1:::0:|:::1:1:0:$x$, $x$:::0:::1f:::1::0:$x$, 2, true, 'approx'),
  ($x$:1:::0:|:::1:1:1:$x$, $x$:::0b:y:1:::1:::0:$x$, 2, true, 'approx'),
  ($x$[[-]]$x$, $x$[[-]gs$x$, 2, true, 'approx'),
  ($x$\n$x$, $x$e$x$, 1, true, 'approx'),
  ($x$\na$x$, $x$ua$x$, 2, true, 'approx'),
  ($x$(a)(b)(c)$x$, $x$nabc$x$, 2, true, 'approx'),
  ($x$xxx$x$, $x$xxxt$x$, 2, true, 'approx'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))$x$, $x$j$x$, 2, true, 'approx'),
  ($x$((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))*$x$, $x$m$x$, 2, true, 'approx'),
  ($x$a?(ab|ba)*$x$, $x$ababababababababababababababababababababaababababababacbababababababababababababa$x$, 2, true, 'approx'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$abebbabbbabbbbbbbabbbbaa$x$, 2, true, 'approx'),
  ($x$abaa|abbaa|abbbaa|abbbbaa$x$, $x$ababbababbabbbabbbbaba$x$, 2, true, 'approx'),
  ($x$aaac|aabc|abac|abbc|baac|babc|bbac|bbbc$x$, $x$baaababac$x$, 2, true, 'approx'),
  ($x$.*$x$, $x$x01\ff$x$, 2, true, 'approx'),
  ($x$aaaa|bbbb|cccc|ddddd|eeeeee|fffffff|gggg|hhhh|iiiii|jjjjj|kkkkk|llll$x$, $x$XaaaXbbbXccXdddXeeeXfffXgbgXhhhXiiiXjjjXkkkXlllXcbaXaaaa$x$, 2, true, 'approx'),
  ($x$a*a*a*a*a*b$x$, $x$aaaaeaajaab$x$, 2, true, 'approx'),
  ($x$abc$x$, $x$abt$x$, 1, true, 'approx'),
  ($x$abc$x$, $x$xabcgy$x$, 2, true, 'approx'),
  ($x$abc$x$, $x$abbc$x$, 2, true, 'approx'),
  ($x$ab*c$x$, $x$atc$x$, 2, true, 'approx'),
  ($x$ab*bc$x$, $x$awc$x$, 2, true, 'approx'),
  ($x$ab*bc$x$, $x$jbbc$x$, 1, true, 'approx'),
  ($x$ab*bc$x$, $x$mabbbgc$x$, 2, true, 'approx'),
  ($x$ab+bc$x$, $x$aybcu$x$, 2, true, 'approx'),
  ($x$ab+bc$x$, $x$abbc$x$, 2, true, 'approx'),
  ($x$ab?bc$x$, $x$abcz$x$, 2, true, 'approx'),
  ($x$ab?bc$x$, $x$abs$x$, 2, true, 'approx'),
  ($x$ab?c$x$, $x$ab$x$, 2, true, 'approx'),
  ($x$a.c$x$, $x$ab$x$, 1, true, 'approx'),
  ($x$a.c$x$, $x$axd$x$, 1, true, 'approx'),
  ($x$a.*c$x$, $x$xyzc$x$, 1, true, 'approx');

-- ----------------------------------------------------------------------------
-- 1. Functional oracle: every case's tre_amatch verdict must equal expect.
--    Report only aggregate pass/fail counts (deterministic), plus the first
--    few mismatches if any, so a regression is actionable without dumping
--    600+ rows.
-- ----------------------------------------------------------------------------
SELECT kind,
       count(*)                                   AS cases,
       count(*) FILTER (WHERE tre_amatch(input, regex, k) = expect) AS passed,
       count(*) FILTER (WHERE tre_amatch(input, regex, k) <> expect) AS failed
FROM tr_corpus
GROUP BY kind
ORDER BY kind;

-- Any individual mismatches (expected to be empty).
SELECT regex, input, k, expect, tre_amatch(input, regex, k) AS got
FROM tr_corpus
WHERE tre_amatch(input, regex, k) <> expect
ORDER BY regex, input, k;

-- ----------------------------------------------------------------------------
-- 2. Coverage guarantee: at least half of all cases are approximate
--    (exercise the edit-distance matcher, pg_tre's reason for existing).
-- ----------------------------------------------------------------------------
SELECT (count(*) FILTER (WHERE kind = 'approx') * 100 / count(*)) >= 50
         AS at_least_half_approx,
       count(*) FILTER (WHERE kind = 'approx') AS approx_cases,
       count(*)                                AS total_cases
FROM tr_corpus;

-- ----------------------------------------------------------------------------
-- 3. Index path agreement: for a deterministic sample, the indexed
--    operator (text %~~ tre_pattern(regex, k)) must return exactly the
--    same row set as the sequential tre_amatch() scan.
-- ----------------------------------------------------------------------------
CREATE TEMP TABLE tr_docs(id serial PRIMARY KEY, body text);
INSERT INTO tr_docs(body)
  SELECT DISTINCT input FROM tr_corpus WHERE input <> '' ORDER BY 1;
CREATE INDEX tr_docs_idx ON tr_docs USING tre (body);

-- Compare seq vs index for a spread of (regex, k) probes drawn from the
-- corpus.  Returns one 'OK'/'BAD' row per probe.
CREATE OR REPLACE FUNCTION tr_probe(pat text, kk int) RETURNS text
LANGUAGE plpgsql AS $$
DECLARE seq_ids int[]; idx_ids int[];
BEGIN
  SET LOCAL enable_indexscan=off; SET LOCAL enable_bitmapscan=off; SET LOCAL enable_seqscan=on;
  EXECUTE format('SELECT array_agg(id ORDER BY id) FROM tr_docs WHERE tre_amatch(body, %L, %s)', pat, kk)
    INTO seq_ids;
  SET LOCAL enable_seqscan=off; SET LOCAL enable_indexscan=on; SET LOCAL enable_bitmapscan=on;
  EXECUTE format('SELECT array_agg(id ORDER BY id) FROM tr_docs WHERE body %%~~ tre_pattern(%L, %s)', pat, kk)
    INTO idx_ids;
  IF seq_ids IS NOT DISTINCT FROM idx_ids THEN RETURN 'OK   k='||kk||'  '||pat; END IF;
  RETURN format('BAD k=%s %s  seq=%s  idx=%s', kk, pat, seq_ids, idx_ids);
END$$;

SELECT tr_probe('a.c', 0);
SELECT tr_probe('a.c', 1);
SELECT tr_probe('(ab|cd)', 0);
SELECT tr_probe('(ab|cd)', 1);
SELECT tr_probe('a[b-d]e', 0);
SELECT tr_probe('a[b-d]e', 2);
SELECT tr_probe('xyz', 0);
SELECT tr_probe('xyz', 1);

RESET client_min_messages;

DROP FUNCTION tr_probe(text, int);
DROP INDEX tr_docs_idx;
DROP TABLE tr_docs;
DROP TABLE tr_corpus;