Pry 수열 변환

Pry 수열은 소문자 알파벳 a부터 z까지만 이어 붙인 문자열이다. 새 Pry 수열을 기록하려면 이미 있는 수열에서 출발해 편집해야 하고, 편집 한 번마다 요금이 붙는다.

각 문자에는 값이 정해져 있다. $\mathrm{val}(a) = 1$, $\mathrm{val}(b) = 2$, $\mathrm{val}(c) = 3$, 같은 식으로 $\mathrm{val}(z) = 26$까지다.

기존 수열을 $A = a_1 a_2 \dots a_n$, 기록하려는 새 수열을 $B = b_1 b_2 \dots b_m$이라고 하자. 쓸 수 있는 편집은 세 가지다.

• 삽입: 원하는 위치에 문자 $x$를 하나 넣는다. 요금은 $1 + \mathrm{val}(x)/100$이다.
• 삭제: 원하는 위치의 문자 하나를 지운다. 요금은 문자와 무관하게 $1$이다.
• 교체: 원하는 위치의 문자 $y$를 문자 $x$로 바꾼다. 요금은 $(\mathrm{val}(x) + \mathrm{val}(y))/10$이다.

예를 들어 ary를 tray로 바꾸는 한 가지 방법은 요금이 3.21이다. t를 넣어 tary를 만들고(1.2), a를 지워 try를 만들고(1), 다시 a를 넣어 tray를 만든다(1.01). 더 싸게 하는 방법도 있다. a를 t로 교체해 try를 만들고(2.1) a를 넣으면(1.01) 요금은 3.11이다.

$A$와 $B$, 그리고 예산 $K$가 주어진다. $A$에서 $B$를 만드는 최소 요금을 구한다. 최소 요금이 $K$보다 크면 그 수열은 아예 기록하지 않으므로, 요금 대신 TOSS를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 이어서 테스트 케이스마다 세 줄이 주어진다.

• 첫 줄에 예산 $K$ (정수, $0 \le K \le 100$)
• 둘째 줄에 기존 Pry 수열 $A$
• 셋째 줄에 새 Pry 수열 $B$

두 수열은 공백이나 구두점 없이 소문자 알파벳만 이어 붙인 형태로 주어지고, 길이는 각각 $1 \le n \le 20000$, $1 \le m \le 20000$을 만족한다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스의 답을 쓴다. 최소 요금이 $K$ 이하이면 그 요금을 소수점 아래 넷째 자리까지 정확히 출력하고, $K$보다 크면 TOSS를 출력한다. 나올 수 있는 요금은 모두 0.01의 배수이므로 넷째 자리까지 쓴 표기는 오차 없이 결정된다.