cyclic-permutations-15

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) ≤ 10^5

SAMPLE INPUT
2
101
101
111
111

SAMPLE OUTPUT
1
3

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: String algorithms


Solutions: