Cyclic Permutations
Problem
Given two binary strings A and B, count how many cyclic permutations of B when taken XOR with A give 0.
Input
First line contains T, the number of testcases. Each testcase consists of two lines, first line contains A and next line contains B.
Output
For each testcase, print required answer in one line.
Constraints
1 ≤ T ≤ 10
1 ≤ length(A) = length(B) ≤ 105
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
Testcase 1:
Three cyclic permutations of string B are 101, 110, 011.
Only one of them gives 0 when taken XOR with A.
Testcase 2:
Three cyclic permutations of string B are 111, 111, 111.
All of them gives 0 when taken XOR with A.
