8x8のチェスの盤上でクイーンは以下のように移動が可能である。

-:移動不可
x:移動可能
Q:クイーン
x-x-x---
-xxx----
xxQxxxxx
-xxx----
x-x-x---
--x--x--
--x---x-
--x----x

※ Qの配置されたマスから縦・横・斜めのすべての方向に何マスでも移動が可能である。

8クイーン問題とは8x8のチェス盤に対しどのクイーンも他のクイーンに一手で移動できない配置にするという問題である。

配置例:
-:空いているマス
Q:クイーン

----Q---
------Q-
Q-------
--Q-----
-------Q
-----Q--
---Q----
-Q------

ここでチェス盤の一部のマスに障害物が存在するとする。
この障害物に対しクイーンは配置することはできず、またクイーンの移動上で衝突する場合はその先に移動することはできない。

例
-:移動不可
x:移動可能
* :障害物
Q:クイーン
x-x-x---
-xxx*---
xxQx****
-xxx*---
x-x-*---
--x**---
--**----
--*-----

この時以下の16x16のチェス盤の中に障害物があるとき最大で何個のクイーンを置くことができるか求めなさい。
チェス盤:queen.txt

またその時のチェス盤の様子を一つ
「-:空いているマス」
「Q:クイーン」
「*:障害物」
(※「-」「Q」「*」は一つのマス)
を使用し16x16のアスキーアートとして示しなさい。