#include "stdafx.h"
#include <cstdlib>
#include <stdio.h>

int m, n, i;

int NWD(int m, int n)
{
	while (n != 0)
	{
		int r;
		r = m % n;
		m = n;
		n = r;

	}
	return m;
}

int _tmain(int argc, _TCHAR* argv[])
{

	signed int t;
	scanf("%d", &t);

		for (i = 1; i <= t; i++)
		{

				scanf("%d", m);
				scanf("%d", n);

				NWD(m, n);

				printf("NWD: %d", m);


		}

	return 0;
}