有一个恶棍殖民地，里面有几个排成一排的洞穴，每个洞穴里恰好住着一个恶棍。 每个殖民地的布局可以用一个长度为偶数的字符串来表示，其中字符串的第i个字符表示第i个洞穴中的恶棍类型。 只有当所有特定类型的恶棍都住在殖民地的前半部分或后半部分时，钢铁侠才能摧毁这个殖民地。 他的助手贾维斯有一种特殊的能力，可以交换任意两个洞穴中的恶棍，即交换字符串中的任何两个字符；他可以进行任意次数的这种操作。 现在，钢铁侠问贾维斯q个问题。在每个问题中，他给贾维斯两个数字x和y。贾维斯必须告诉钢铁侠，从原来的殖民地布局开始，使用他的能力可以创建多少不同的殖民地布局，使得所有与原来第x个洞穴或第y个洞穴中相同的类型的恶棍都生活在同一半边，并且钢铁侠可以摧毁这些殖民地布局。 如果两个殖民地布局存在一个洞穴，使得该洞穴中不同类型的恶棍存在于这两个布局中，则认为这两个殖民地布局是不同的。 输入格式 第一行包含一个字符串s（2 ≤ |s| ≤ 10^5），表示初始殖民地布局。字符串s可以同时包含小写和大写英文字母，且其长度为偶数。