// The Code uses Euclidean Algorithm to find all the C-Strings of length |S| with exactly X HUMONGOUS Subsequences instead
// of iterating over all possible C-Strings and calculating the answer for each of them and finding their minima.
// Intended Total Complexity:- O(T*(X*LogX + ALPHA*(LogX + |S|))) where ALPHA is quite less but not determinable.
// SAJAL AGRAWAL.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string.h>
#define ll long long
#ifndef ONLINE_JUDGE
    #define gc getchar
#else
    #define gc getchar_unlocked
#endif
#ifndef ONLINE_JUDGE
    #define pc putchar
#else
    #define pc putchar_unlocked
#endif
using namespace std;
int read_int()
{
  int f=0;
  char c = gc();
  if(c=='-')
  f=1;
  while(c<'0' || c>'9')
  c = gc();
  int ret = 0;
  while(c>='0' && c<='9')
  {
    ret = 10 * ret + c - 48;
    c = gc();
  }
  if(!f)
  return ret;
  else
  return (-ret);
}
void write_int(int n)
{
    int N = n, rev, count = 0,g=0;
    if(N<0)
    {
        g=1;
        N=-N;
    }
    rev = N;
    if (N == 0)
    {
        pc('0');
        pc(' ');
        return ;
    }
    while ((rev % 10) == 0)
    {
        count++;
        rev /= 10;
    }
    rev = 0;
    while (N != 0)
    {
        rev = (rev<<3) + (rev<<1) + N % 10;
        N /= 10;
    }
    if(g==1)
    pc('-');
    while (rev != 0)
    {
        pc(rev % 10 + '0');
        rev /= 10;
    }
    while (count--)
    pc('0');
    pc(' ');
}
vector < pair < int,int > > onero;
vector < int > is;
int l;
int Hums(int a,int b,int k)          //Function to perform the eculidean algorithm for finding the intended length string
{
    int xx=a;
    int yy=b;
	int rt=0;
	int r;
	int k1=0;
	while(a!=1)
	{
		r=b%a;
		if(r==0&&a!=1)
        return 0;
		rt+=b/a;
		if(k==1)
		{
			if(k1==0)
			{
				onero.push_back(make_pair(b/a,0));
				k1=1;
			}
			else
			{
				onero.push_back(make_pair(b/a,1));
				k1=0;
			}
		}
		b=a;                //The Common operations of the Euclidean Algo
		a=r;
	}
	rt+=b-1;
	if(k==1)
	{
		if(k1==0)
		onero.push_back(make_pair(b-1,0));
		else
		onero.push_back(make_pair(b-1,1));
	}
	if(rt==l-1&&k==0)
    {
        is.push_back(xx);
        is.push_back(yy-xx);
    }
}
int i,j,k;
char str[35]={'\0'};
main()
{
	int t=read_int();
	while(t--)
	{
		onero.clear();
		is.clear();
		cin>>str;
		int x=read_int();
		int i=0;
		while(str[i]!='\0')
        i++;
        l=i;
		x++;
		for(i=1;i<=x/2;i++)
        Hums(i,x,0);                              //Calling the Eucledian function so as to see all C-Strings with X HUMONGOUS subsequences and |S| length
		int minans=33;
		for(i=0;i<is.size();i++)
        {
            onero.clear();
            Hums(is[i],x,1);        //Calling the Eucledian function again so as to work upon the previously calculated strings to count the flips
            int index=1;
            int ans=0;
            for(j=onero.size()-1;j>=0;j--)
            {
                int limit=onero[j].first;
                int ch=onero[j].second;
                for(k=1;k<=limit;k++)
                {
                    ans+=((int)(str[index])-48)^ch;       //Counting Flips for a particular C-String
                    index++;
                }
            }
            minans=min(minans,ans);     //Minimum flips among all those flips
        }
        if(minans==33)
        cout<<"NO\n";
        else
        cout<<"YES\n"<<minans<<"\n";
	}
}