На планете AMI-1511 живёт мальчик Айрат. У каждого из жителей этой планеты есть свое хобби, в частности, Айрат любит бегать, причём не просто так — он мечтает превратить бег в настоящее искусство.

Для начала Айрат хочет сконструировать беговой трек с полотном t. Полотно для трека на AMI-1511 — последовательность из цветных блоков, где каждый блок обозначается строчной английской буквой. Таким образом, любое полотно представляется как строка некоторой длины. К сожалению, блоки отсутствуют в свободной продаже.

Айрат нашёл в магазине неограниченное количество полотен для трека s, а ещё у него есть ножницы и клей. Айрат может купить некоторое количество полотен s, после чего вырезать из каждого ровно один непрерывный кусок (подстроку) и приклеить его в конец своего полотна, при этом он может развернуть новый кусок перед приклеиванием. Помогите Айрату посчитать, сколько минимум полотен s ему нужно купить, какие куски из них вырезать и в каком порядке склеить, чтобы получить желанное полотно t.