You are given two binary strings x and y, which are binary representations of some two integers (let's denote these integers as f(x) and f(y)). You can choose any integer k ≥ 0, calculate the expression s_k = f(x) + f(y) ⋅ 2^k and write the binary representation of s_k in reverse order (let's denote it as rev_k). For example, let x = 1010 and y = 11; you've chosen k = 1 and, since 2^1 = 10_2, so s_k = 1010_2 + 11_2 ⋅ 10_2 = 10000_2 and rev_k = 00001.

For given x and y, you need to choose such k that rev_k is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, k exists and is finite.

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of queries.

Next 2T lines contain a description of queries: two lines per query. The first line contains one binary string x, consisting of no more than 10^5 characters. Each character is either 0 or 1.

The second line contains one binary string y, consisting of no more than 10^5 characters. Each character is either 0 or 1.

It's guaranteed, that 1 ≤ f(y) ≤ f(x) (where f(x) is the integer represented by x, and f(y) is the integer represented by y), both representations don't have any leading zeroes, the total length of x over all queries doesn't exceed 10^5, and the total length of y over all queries doesn't exceed 10^5.

Output

Print T integers (one per query). For each query print such k that rev_k is lexicographically minimal.

Example

Input


4
1010
11
10001
110
1
1
1010101010101
11110000


Output


1
3
0
0

Note

The first query was described in the legend.

In the second query, it's optimal to choose k = 3. The 2^3 = 1000_2 so s_3 = 10001_2 + 110_2 ⋅ 1000_2 = 10001 + 110000 = 1000001 and rev_3 = 1000001. For example, if k = 0, then s_0 = 10111 and rev_0 = 11101, but rev_3 = 1000001 is lexicographically smaller than rev_0 = 11101.

In the third query s_0 = 10 and rev_0 = 01. For example, s_2 = 101 and rev_2 = 101. And 01 is lexicographically smaller than 101.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.io.ObjectInputStream.GetField;
import java.security.KeyStore.Entry;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class codeforcesreturn {
	public static class Pair implements Comparable<Pair> {
		String name;
		int prnum;
		int pen;

		public Pair(String n, int pr, int pe) {
			name = n;
			prnum = pr;
			pen = pen;
		}

		@Override
		public int compareTo(Pair p) {
			if (prnum == p.prnum)
				return pen - p.pen;
			return p.prnum - prnum;
		}

	}

	public static class UnionFind {
		int[] p, rank;
		boolean[] cyclic;

		public UnionFind(int N) {
			p = new int[N];
			rank = new int[N];
			// cyclic = new boolean[N];
			for (int i = 0; i < N; i++)
				p[i] = i;
		}

		public int findSet(int x) {
			return p[x] == x ? x : (p[x] = findSet(p[x]));
		}

		public boolean isunioned(int x, int y) {
			return findSet(x) == findSet(y);
		}

		public boolean union(int x, int y) {
			x = findSet(x);
			y = findSet(y);
			if (x == y) {
				return false;
			}
			if (rank[x] > rank[y])
				p[y] = x;
			else {
				p[x] = y;
				if (rank[x] == rank[y])
					++rank[y];
			}
			return true;
		}
	}

	static ArrayList<Integer>[] adjlist;
	static int[][] adjmatrix;
	static int[][] adjmatrix2;
	static boolean[] vis;
	static boolean[] intialvis;
	static boolean[] vis2;
	static Stack<Integer> st;
	static ArrayList<Integer> arrylist;
	static boolean flag;
	static int[] dx = new int[] { 1, -1, 0, 0 };
	static int[] dy = new int[] { 0, 0, 1, -1 };
	static int[] Arr;
	static boolean ans = true;;
	static int[] dist, parent;
	static boolean[] visited;
	static int src, dest;

	public static void SSSP_BFS(int u) {

		src = u;
		Queue<Integer> q = new LinkedList<>();
		visited = new boolean[adjList.length];
		dist = new int[adjList.length];
		parent = new int[adjList.length];
		dist[u] = 0;
		parent[u] = -1;
		visited[u] = true;
		q.add(u);
		while (!q.isEmpty()) {
			int num = q.poll();
			for (int v : adjList[num]) {
				if (!visited[v]) {
					visited[v] = true;
					q.add(v);
					parent[v] = num;
					dist[v] = dist[num] + 1;
				}
			}
		}
	}

	public static void getPath(int u) {// u is the destination in the
										// initial call
		if (u == src) {
			System.out.print(src + " ");
			return;
		}
		getPath(parent[u]);
		System.out.print(u + " ");
	}

	static int INF = (int) 1e9;// to avoid overflow
	static ArrayList<Pair>[] adjListWeighted;

	/*
	 * public static void SSSP_dijkstra(int src) {// O(Elog(E))
	 * PriorityQueue<Pair> pq = new PriorityQueue<>(); dist = new
	 * int[adjListWeighted.length]; Arrays.fill(dist, INF); dist[src] = 0;
	 * pq.add(new Pair(src, 0)); while (!pq.isEmpty()) { Pair curr =
	 * pq.remove(); if (dist[curr.node] < curr.weight) // because u may have //
	 * different paths with diff // weights so u just process // this path if
	 * it's better // than what we originally // have continue; for (Pair p :
	 * adjListWeighted[curr.node]) { if (dist[p.node] > curr.weight + p.weight)
	 * { dist[p.node] = p.weight + curr.weight; // p.weight+=curr.weight;//this
	 * will change in ur // original graph if u want it again if u don't want so
	 * // use new Pair()
	 * 
	 * pq.add(new Pair(p.node, dist[p.node])); // pq.add(new //
	 * Pair(p.node,p.weight+next.weight)); // it's // equivalent to // this but
	 * to // save some // memory
	 * 
	 * } } }
	 * 
	 * }
	 * 
	 */
	public static long gcd(long u, long v) {
		if (u == 0)
			return v;
		return gcd(v % u, u);
	}

	public static long power(long u, long v) {
		long ans = 1;
		for (int i = 0; i < v; i++) {
			ans *= u;
			ans %= 998244353l;
		}
		return ans;
	}

	public static void bib(int u) {

		vis[u] = true;
		for (int v : adjlist[u]) {
			if (!vis[v]) {
				counter[v] = 1 ^ counter[u];
				bib(v);
			} else if (counter[v] != (1 ^ counter[u]))
				ans = false;

		}
	}

	static int n, m;
	static int[] rock, sc, pap;
	static long[][] memo;

	/*
	 * public static long dp(int type, int lastidx) { if (type == 2) { if (sc[n]
	 * - sc[lastidx - 1] > 0) return sc[n] - sc[lastidx - 1]; } }
	 */
	public static long cieel(long n, long d) {
		if (n % d == 0)
			return n / d;
		return (n / d) + 1;
	}

	static ArrayList<Integer>[] adjList;
	static int V, E, counter[], c, SCC, dfs_num[], dfs_low[];
	static int[] inSCC, cost;
	static Stack<Integer> stack;
	static PrintWriter pw;
	static long minn = 0, num = 1;

	static void tarjanSCC() // O(V + E)
	{
		for (int i = 0; i < V; ++i)
			if (dfs_num[i] == 0)
				tarjanSCC(i);
	}

	static void tarjanSCC(int u) {
		dfs_num[u] = dfs_low[u] = ++c;
		stack.push(u);

		for (int v : adjList[u]) {
			if (dfs_num[v] == 0)
				tarjanSCC(v);
			if (inSCC[v] == -1)
				dfs_low[u] = Math.min(dfs_low[u], dfs_low[v]);
		}
		if (dfs_num[u] == dfs_low[u]) {
			// SCC found
			SCC++;
			long min = cost[u];
			long numberofmin = 1;
			while (true) {
				int v = stack.pop();
				inSCC[v] = u;
				if (v == u)
					break;
				int cos = cost[v];
				if (cos < min) {
					min = cos;
					numberofmin = 1;
				} else if (cos == min)
					numberofmin++;
			}
			minn += min;
			num *= numberofmin;
			num %= 1000000007;
		}
	}

	public static void main(String[] args) throws IOException, InterruptedException {
		// FileWriter f = new FileWriter("C:\\Users\\Hp\\Desktop\\out.txt");
		// PrintWriter pw = new PrintWriter(f);
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		outer: while (t-- > 0) {
			String str1=sc.next();
			String str2=sc.next();
			int ans=0;
			int idx=0;
			for(int i=str2.length()-1;i>=0;i--){						
				if(str2.charAt(i)=='1'){
					break;
				}
				idx++;
			}
			for(int i=str1.length()-1-idx;i>=0;i--){
				
				if(str1.charAt(i)=='1'){
					break;
				}
				ans++;
			}
			pw.println(ans);
		}
		pw.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}