Toyuq fermeri Xioyan üç yeni toyuq - Lüsi, Çarli və CC aldı. Xioyan elə çəpər çəkmək istəyir ki, onların hər birinin öz xüsusi sərbəst, maneəsiz görünüşlü ərazisi olsun. Çəpərin üç tərəfi olmalıdır; bu, hər toyuğa o birilərə mane olmamaqla öz çəpərinin tərəfi ilə irəli-geri gəzişməyə imkan verir. Xioyan anbardan uzunluğu dəqiq p fut olan rulon şəklində məftiltor (çəpər) tapdı. Xioyan bütün rulondan tam istifadə etməklə və perimetrləri tam ədəd olmaqla toyuqlar üçün çəpər qurma üsullarının sayını hesablamaq istəyir. Fırlanmaqla alınan çəpərlər eyni hesab edilir. Amma güzgü əksi ilə alınan çəpərlər müxtəlif ola bilər (aşağıdakı şəklə bax).

Giriş verilənləri

Birinci sətirdə testlərin t (1 ≤ t ≤ 1000) sayı yerləşir. Hər bir test o birilərdən asılı olmadan emal edilməlidir.

Hər bir test bir sətirdə iki ədəd şəklində verilir: testin nömrəsi və tor rulonunun n (3 ≤ n ≤ 10000) uzunluğu.

Çıxış verilənləri

Hər bir test üçün bir sətirdə testin nömrəsini və bütün rulondan tam istifadə etməklə və toyuqlar üçün üçtərəfli müxtəlif çəpər qurma üsullarının sayı verilir.