#include <bits/stdc++.h>
using namespace std;
long long mult(long long a, long long b, long long p = 1000000007) {
  return ((a % p) * (b % p)) % p;
}
long long multbig(long long a, long long b, long long mod = 1000000007) {
  if (a == 0 or b == 0) return 0;
  if (a == 1 or b == 1) return (a * b) % mod;
  long long cur = multbig(a, b / 2, mod);
  cur = (2 * cur) % mod;
  if (b % 2) cur = (cur + a) % mod;
  return cur;
}
long long add(long long a, long long b, long long p = 1000000007) {
  if (a >= p) a %= p;
  if (b >= p) b %= p;
  if (a + b > p)
    return (a + b) % p;
  else
    return a + b;
}
long long sub(long long a, long long b, long long p = 1000000007) {
  return (a % p - b % p + p) % p;
}
long long fpow(long long n, long long k, long long p = 1000000007) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = mult(r, n, p);
    n = mult(n, n, p);
  }
  return r;
}
long long inv(long long a, long long p = 1000000007) {
  return fpow(a, p - 2, p);
}
long long inv_euclid(long long a, long long m = 1000000007) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
int isPowerof2(long long x) { return (x && !(x & (x - 1))); }
long long log2(long long x) {
  long long res = 0;
  while (x >>= 1) res++;
  return res;
}
bool isPerfectSquare(long double x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
bool check(long long i, long long j, long long n, long long m) {
  return (i >= 0 && i < n && j >= 0 && j < m);
}
string s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
long long ceil(const long long &a, const long long &b) {
  return (a - 1) / b + 1;
}
bool comp(tuple<long long, string, string> a,
          tuple<long long, string, string> b) {
  if (get<0>(a) > get<0>(b)) return true;
  return false;
}
bool comp2(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.second < b.second) {
    return true;
  } else if (a.second == b.second) {
    if (a.first > b.first)
      return true;
    else
      return false;
  } else
    return false;
}
void convert(int arr[], int n) {
  int temp[n + 1];
  for (int i = 1; i <= n; i++) temp[i] = arr[i];
  sort(temp + 1, temp + n + 1);
  unordered_map<int, int> umap;
  int val = 1;
  for (int i = 1; i <= n; i++) umap[temp[i]] = val++;
  for (int i = 1; i <= n; i++) arr[i] = umap[arr[i]];
}
bool prime[10000005];
void SieveOfEratosthenes(int n) {
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = 0;
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true)
      for (int i = p * p; i <= n; i += p) prime[i] = false;
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int ok = 1;
    vector<int> v;
    for (int i = 0; i < s.size() - 1; i++) {
      if (s[i] == s[i + 1] && s[i] != '?') {
        ok = 0;
        break;
      }
    }
    if (!ok)
      cout << -1 << "\n";
    else {
      for (int i = 0; i < s.size(); i++) {
        if (s[i] == '?') {
          for (char p = 'a'; p <= 'c'; p++) {
            if (s[i - 1] != p && s[i + 1] != p) {
              s[i] = p;
            }
          }
        }
      }
      cout << s << "\n";
    }
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

A string is called beautiful if no two consecutive characters are equal. For example, "ababcb", "a" and "abab" are beautiful strings, while "aaaaaa", "abaa" and "bb" are not.

Ahcl wants to construct a beautiful string. He has a string s, consisting of only characters 'a', 'b', 'c' and '?'. Ahcl needs to replace each character '?' with one of the three characters 'a', 'b' or 'c', such that the resulting string is beautiful. Please help him!

More formally, after replacing all characters '?', the condition s_i ≠ s_{i+1} should be satisfied for all 1 ≤ i ≤ |s| - 1, where |s| is the length of the string s.

Input

The first line contains positive integer t (1 ≤ t ≤ 1000) — the number of test cases. Next t lines contain the descriptions of test cases.

Each line contains a non-empty string s consisting of only characters 'a', 'b', 'c' and '?'. 

It is guaranteed that in each test case a string s has at least one character '?'. The sum of lengths of strings s in all test cases does not exceed 10^5.

Output

For each test case given in the input print the answer in the following format:

  * If it is impossible to create a beautiful string, print "-1" (without quotes); 
  * Otherwise, print the resulting beautiful string after replacing all '?' characters. If there are multiple answers, you can print any of them. 

Example

Input


3
a???cb
a??bbc
a?b?c


Output


ababcb
-1
acbac

Note

In the first test case, all possible correct answers are "ababcb", "abcacb", "abcbcb", "acabcb" and "acbacb". The two answers "abcbab" and "abaabc" are incorrect, because you can replace only '?' characters and the resulting string must be beautiful.

In the second test case, it is impossible to create a beautiful string, because the 4-th and 5-th characters will be always equal.

In the third test case, the only answer is "acbac".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long mult(long long a, long long b, long long p = 1000000007) {
  return ((a % p) * (b % p)) % p;
}
long long multbig(long long a, long long b, long long mod = 1000000007) {
  if (a == 0 or b == 0) return 0;
  if (a == 1 or b == 1) return (a * b) % mod;
  long long cur = multbig(a, b / 2, mod);
  cur = (2 * cur) % mod;
  if (b % 2) cur = (cur + a) % mod;
  return cur;
}
long long add(long long a, long long b, long long p = 1000000007) {
  if (a >= p) a %= p;
  if (b >= p) b %= p;
  if (a + b > p)
    return (a + b) % p;
  else
    return a + b;
}
long long sub(long long a, long long b, long long p = 1000000007) {
  return (a % p - b % p + p) % p;
}
long long fpow(long long n, long long k, long long p = 1000000007) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = mult(r, n, p);
    n = mult(n, n, p);
  }
  return r;
}
long long inv(long long a, long long p = 1000000007) {
  return fpow(a, p - 2, p);
}
long long inv_euclid(long long a, long long m = 1000000007) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
int isPowerof2(long long x) { return (x && !(x & (x - 1))); }
long long log2(long long x) {
  long long res = 0;
  while (x >>= 1) res++;
  return res;
}
bool isPerfectSquare(long double x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
bool check(long long i, long long j, long long n, long long m) {
  return (i >= 0 && i < n && j >= 0 && j < m);
}
string s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
long long ceil(const long long &a, const long long &b) {
  return (a - 1) / b + 1;
}
bool comp(tuple<long long, string, string> a,
          tuple<long long, string, string> b) {
  if (get<0>(a) > get<0>(b)) return true;
  return false;
}
bool comp2(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.second < b.second) {
    return true;
  } else if (a.second == b.second) {
    if (a.first > b.first)
      return true;
    else
      return false;
  } else
    return false;
}
void convert(int arr[], int n) {
  int temp[n + 1];
  for (int i = 1; i <= n; i++) temp[i] = arr[i];
  sort(temp + 1, temp + n + 1);
  unordered_map<int, int> umap;
  int val = 1;
  for (int i = 1; i <= n; i++) umap[temp[i]] = val++;
  for (int i = 1; i <= n; i++) arr[i] = umap[arr[i]];
}
bool prime[10000005];
void SieveOfEratosthenes(int n) {
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = 0;
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true)
      for (int i = p * p; i <= n; i += p) prime[i] = false;
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int ok = 1;
    vector<int> v;
    for (int i = 0; i < s.size() - 1; i++) {
      if (s[i] == s[i + 1] && s[i] != '?') {
        ok = 0;
        break;
      }
    }
    if (!ok)
      cout << -1 << "\n";
    else {
      for (int i = 0; i < s.size(); i++) {
        if (s[i] == '?') {
          for (char p = 'a'; p <= 'c'; p++) {
            if (s[i - 1] != p && s[i + 1] != p) {
              s[i] = p;
            }
          }
        }
      }
      cout << s << "\n";
    }
  }
}

```