def check(x):
    s = str(x)
    cnt = 0
    for c in s:
        if c != '0':
            cnt += 1
    return cnt == 1

a = []
for i in range(1, 1000000):
    if check(i):
        a.append(i)
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    for x in a:
        if x <= n:
            ans += 1
    print(ans)

for _ in range(int(input())):
	n = int(input())
	s = input()
	cur = {}
	for i in range(n - 1):
		t = s[i:i+2]
		if t in cur:
			if cur[t] < i - 1:
				print("YES")
				break
		else:
			cur[t] = i
	else:
		print("NO")

for _ in range(int(input())):
	n = int(input())
	s = [input() for i in range(2)]
	pos = -1
	for i in range(n):
		if s[0][i] != s[1][i]:
			pos = i
	if pos == -1:
		print("YES")
		continue
	ok = True
	cur = 0 if s[0][pos] == 'B' else 1
	for i in range(pos + 1, n):
		if s[cur][i] == 'W':
			ok = False
		if s[cur ^ 1][i] == 'B':
			cur ^= 1
	cur = 0 if s[0][pos] == 'B' else 1
	for i in range(pos - 1, -1, -1):
		if s[cur][i] == 'W':
			ok = False
		if s[cur ^ 1][i] == 'B':
			cur ^= 1
	print("YES" if ok else "NO")

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

const int INF = int(1e9);
const int N = int(1e7) + 5;

int mind[N];

void precalc() {
	fore (i, 0, N)
		mind[i] = i;
	
	for (int p = 2; p < N; p++) {
		if (mind[p] != p)
			continue;
		for (int d = 2 * p; d < N; d += p)
			mind[d] = min(mind[d], p);
	}
}

int x, y;

inline bool read() {
	if(!(cin >> x >> y))
		return false;
	return true;
}

vector<int> getPrimes(int v) {
	vector<int> ps;
	while (v > 1) {
		if (ps.empty() || ps.back() != mind[v])
			ps.push_back(mind[v]);
		v /= mind[v];
	}
	return ps;
}

inline void solve() {
	int d = y - x;
	if (d == 1) {
		cout << -1 << '\n';
		return;
	}
	
	int r = INF;
	for (int p : getPrimes(d))
		r = min(r, ((x + p - 1) / p) * p);
	cout << r - x << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	precalc();
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

int n;
int v[N];
map<vector<int>, long long> dp[N];

pair<int, vector<int>> go(vector<int> a, int x)
{
    if(x == 0)
        return {1, a};
    else
    {
        bool f = false;
        for(int i = 0; i < a.size() && !f; i++)
            if((a[i] & x) > 0)
            {
                f = true;
                a[i] = x;
            }
        int c = 0;
        if(!f)
        {
            c = 1;
            a.push_back(x);
        }
        return {c, a};
    }
}

long long calc(int i, vector<int> a)
{
    if(i == n) return 0ll;
    if(dp[i].count(a)) return dp[i][a];
    auto p = go(a, v[i]);
    return (dp[i][a] = p.first * 1ll * (n - i) + calc(i + 1, p.second));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &v[i]);
    long long ans = 0;
    for(int i = 0; i < n; i++)
        ans += calc(i, vector<int>(0));
    printf("%lld\n", ans);    
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 243;

struct edge
{
    int y, c, w, f;
    edge() {};
    edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
};

vector<edge> e;
vector<int> g[N];

int rem(int x)
{
    return e[x].c - e[x].f;
}

void add_edge(int x, int y, int c, int w)
{
    g[x].push_back(e.size());
    e.push_back(edge(y, c, w, 0));
    g[y].push_back(e.size());
    e.push_back(edge(x, 0, -w, 0));
}

int n, m, s, t, v;

pair<int, long long> MCMF()
{
    int flow = 0;
    long long cost = 0;
    while(true)
    {
        vector<long long> d(v, (long long)(1e18));
        vector<int> p(v, -1);
        vector<int> pe(v, -1);
        queue<int> q;
        vector<bool> inq(v);
        q.push(s);
        inq[s] = true;
        d[s] = 0;
        while(!q.empty())
        {
            int k = q.front();
            q.pop();
            inq[k] = false;
            for(auto ei : g[k])
            {
                if(rem(ei) == 0) continue;
                int to = e[ei].y;
                int w = e[ei].w;
                if(d[to] > d[k] + w)
                {
                    d[to] = d[k] + w;
                    p[to] = k;
                    pe[to] = ei;
                    if(!inq[to])
                    {
                        inq[to] = true;
                        q.push(to);
                    }
                }
            }
        }
        if(p[t] == -1 || d[t] >= 0) break;
        flow++;
        cost += d[t];
        int cur = t;
        while(cur != s)
        {
            e[pe[cur]].f++;
            e[pe[cur] ^ 1].f--;
            cur = p[cur];
        }
    }
    return make_pair(flow, cost);
}

void no_answer()
{
    cout << "Impossible" << endl;
    exit(0);
}

int main()
{                              
    cin >> n >> m;
    vector<int> excess_flow(n, 0);
    vector<int> orc(m);
    for(int i = 0; i < m; i++)
    {
        int x, y, c, w;
        cin >> x >> y >> c >> w;
        orc[i] = c;
        --x;
        --y;
        add_edge(x, y, c / 2, w);
        if(c % 2 == 1)
        {
            excess_flow[x]--;
            excess_flow[y]++;
        }
    }
    s = n;
    t = n + 1;
    v = n + 2;
    int total_excess = 0;
    if(excess_flow[0] % 2 == -1)
    {
        excess_flow[0]--;
        excess_flow[n - 1]++;
    }
    for(int i = 0; i < n; i++)
    {
        if(excess_flow[i] % 2 != 0)
            no_answer();
        int val = abs(excess_flow[i]) / 2;
        if(excess_flow[i] > 0)
        {
            total_excess += val;
            add_edge(s, i, val, -int(1e9));
        }
        if(excess_flow[i] < 0)
        {
            add_edge(i, t, val, -int(1e9));
        }
    }
    add_edge(s, 0, 100000, 0);
    add_edge(n - 1, t, 100000, 0);
    auto ans = MCMF();
    bool good_answer = true;
    for(int x = 0; x < e.size(); x++)
        if(e[x].w == -int(1e9) && rem(x) != 0)
            good_answer = false;
    if(!good_answer)
        no_answer();
    cout << "Possible" << endl;
    for(int i = 0; i < 2 * m; i += 2)
    {
        if(i) cout << " ";
        cout << e[i].f * 2 + orc[i / 2] % 2;
    }
    cout << endl;
}