Berúthiel

The dark and mournful Queen to Tarannon Falastur, the twelfth King of Gondor. She owned ten marvellous and magical cats, that she set to spy on the doings of the people of Gondor. Her scheming was her undoing, though, since her husband set her adrift on the Great Sea, with only her cats for company. She sailed into the far south and was never heard of again, but she and her mysterious cats lived on in legend for millennia.

(Note that these details come from an unpublished manuscript quoted by Christopher Tolkien in Unfinished Tales of Númenor and Middle-earth, and so their canonicity is not certain.)