SP23925 VAPI01 - Vitaliy and Pie

经过了一天的忙碌，维塔利感到非常饥饿，想要尽快吃到他最爱的土豆派。然而，这需要他穿过房子的多个房间，解决一些难题。维塔利目前在一排共 _n_ 个房间中的第一个房间，房间从左到右依次编号为 1 到 _n_。他只能按顺序从一个房间走到下一个房间，直到到达最后一个房间。 土豆派被放在第 _n_ 个房间，所以维塔利必须到那里才能吃到它。 每对相邻房间之间都有一扇上锁的门。要进入房间 _x_，他需要用钥匙打开从房间 _x_ - 1 到房间 _x_ 的门。 房子里存在多种类型的门（用大写英文字母表示）和钥匙（用小写英文字母表示）。一种类型为 _t_ 的钥匙可以打开一种类型为 _T_ 的门，前提是 _t_ 和 _T_ 是相同的字母，只是大小写不同。例如，钥匙 "f" 可以打开门 "F"。 头 _n_ - 1 个房间中，各有一个可用钥匙，可以帮助维塔利打开进入下一个房间的门。但每次开完门后，维塔利不会带走钥匙，他直接跑进下一个房间。因此，每把钥匙最多只能开一扇门。 维塔利担心，他可能会遇到没有合适钥匙开门的情况。为了确保能顺利到达第 _n_ 个房间，开始旅行前，维塔利可以购买任意数量的任意类型的钥匙。 给定房间的布局图，维塔利想知道，至少需要购买多少把钥匙，才能百分之百确保到达装有美味土豆派的第 _n_ 个房间。请帮助维塔利找出这个最少的钥匙数量。

第一行是一个整数 $t$，表示测试用例的数量。 接下来的每个测试用例包含以下两行信息： - 第一行是一个正整数 $n$，表示房子的房间数量。 - 第二行是一个长度为 $2 \cdot n - 2$ 的字符串 $s$，定义了房间之间以及房间中的钥匙和门的类型。字符串中奇数位置为小写字母，代表放在相应房间的钥匙类型；偶数位置为大写字母，代表相应门的类型。

对于每个测试用例，输出一个整数，表示维塔利至少需要购买的钥匙数量，才能确保能够到达第 _n_ 个房间。

- $1 \le t \le 100$ - $2 \le n \le 5$ **本翻译由 AI 自动生成**