Shift String

AtCoder

IDabc430_e

Time2000ms

Memory256MB

Difficulty—

You are given strings $A$ and $B$ of equal length consisting of `0` and `1`. You can perform the following operation on $A$ zero or more times. * Move the first character of $A$ to the end. Find the minimum number of operations required to make $A=B$. If it is impossible to make $A=B$ no matter how you operate, print $-1$ instead. You are given $T$ test cases; find the answer for each of them. ## Constraints * $1 \le T \le 10000$ * $A$ and $B$ are strings consisting of `0` and `1`. * $2 \le |A|=|B| \le 10^6$ * For a single input, the sum of $|A|$ does not exceed $10^6$. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $A$ $B$ [samples]

Samples

Input #1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Output #1

2
-1
0
-1
22

This input contains five test cases.

*   For the first test case, $A=$ `1010001` and $B=$ `1000110`.
    *   By performing the operation on $A$ twice, $A$ becomes `1010001` $\rightarrow$ `0100011` $\rightarrow$ `1000110`, which makes $A=B$.
*   For the second test case, no matter how you perform the operation, you cannot change `000` to `111`.
*   For the third test case, $A=B$ from the beginning.

API Response (JSON)

{
  "problem": {
    "name": "Shift String",
    "description": {
      "content": "You are given strings $A$ and $B$ of equal length consisting of `0` and `1`. You can perform the following operation on $A$ zero or more times. *   Move the first character of $A$ to the end. Find t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc430_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given strings $A$ and $B$ of equal length consisting of `0` and `1`.\nYou can perform the following operation on $A$ zero or more times.\n\n*   Move the first character of $A$ to the end.\n\nFind t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments