Sample Input 1

8
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 2

Sample Output 1

2
2
2
3
4
6
8

Giải thích:

Các chuỗi mới được tạo sau mỗi lần nối là: 00, 10, 00, 100, 1000, 001000 và 00100010.

Các giá trị palindromic tương ứng được đưa ra trong đầu ra ví dụ. Ví dụ. giá trị palindromic của 00100010 là 8 vì chuỗi chứa 8 chuỗi con palindromic: 0, 00, 000, 10001, 0100010, 1, 010, 00100.